Non abbiamo notizie certe sulla sua origine, ma le due finestre bifore della parte ovest ci lasciano intuire che il nucleo principale sia stato edificato molto probabilmente durante il periodo normanno-svevo.
Tale sito nel corso della storia dell'abitato ha avuto di sicuro una funzione molto rilevante tanto da dare il nome al paese. E' certo che Castiglione nel XII secolo viene chiamato Quastallum da Edrisi, Castillo in un diploma di Ruggero II, Castillio in un diploma di Papa Eugenio III.
L'attuale nome, invece, significa Castello grande. Al latino medievale castellum, infatti è stato aggiunto il suffisso accrescitivo ione, facendolo diventare Castellione, che gli aragonesi prima e gli spagnoli poi pronunziavano Casteglione. Il termine ben presto comunque interpretato come Castello del Leone per offrire al paese un marchio di regalità, dando luogo anche allo stemma: un castello e due leoni accovacciati.
Il castello nel Medioevo, collegato alla roccaforte del Castelluccio e ad un avamposto identificabile con la chiesa di San Pietro era messo in comunicazione con questi da passaggi sotterranei, che giungevano, si dice, fino al Cannizzo. Essi costituivano un vero e proprio complesso architettonico e difensivo, ed un vecchio stemma cinquecentesco della città, con tre torri, mette in evidenza la loro importanza. I vari quartieri del castello assumevano funzioni diverse. Vi era la parte più nobile riservata al castellano; vi erano le scuderie, i fienili, le stalle, le abitazioni per i servi e per gli addetti alla manutenzione; vi erano le carceri, all'interno delle quali, nelle scomode celle dette dammusi, lunghe non più di due metri ed alte appena un metro, venivano rinchiusi spesso i più facinorosi avversari politici e più incalliti delinquenti; vi erano le cisterne per conservare l'acqua piovana o per nascondervi, durante gli assedi, vettovaglie e suppellettili preziosi; vi erano le rotonde bombe di pietra, pronte per essere scagliate contro i nemici; vi era nella parte più alata un ampio locale, detta Solecchia, che comunemente si ritiene fosse la zecca dove si coniavano le monete, ma poteva essere il luogo dove il feudatario si riparava dal sole, dopo aver completato quasi per intero il suo vastissimo feudo.