Risalgono ad epoca normanna le prime interessanti informazioni relative tanto all'insediamento, quanto al castello medievale di Lentini. La testimonianza più importante è quella di Ugo Falcando, il quale ricorda la devastazione dell'abitato in occasione del terremoto del 1169. Alla metà del XII sec. Edrisi scrive della città come ricca di mercati, di corsi d'acqua e avente un fertile territorio circostante (Amari M., BAS, vol. I, pag. 72); inoltre definisce l'abitato "hisn", forte rocca. L'aggettivo starebbe ad indicare che già in epoca normanna esisteva una fortezza a salvaguardia del paese, il quale a sua volta possedeva certamente una cinta muraria. Con grande probabilità la fortezza sorgeva sul colle "Castellaccio", ove oggi si possono osservare i resti di un esteso complesso edilizio, ristrutturato durante la prima metà del XIII sec. d.C., secondo volontà di Federico II, il quale lascia ampia testimonianza dell'operato in una celebre epistola, indirizzata a Riccardo da Lentini. Lo scritto è breve, ma esauriente nei contenuti: si rinnovano le mura del castello per mezzo di blocchi calcarei squadrati, "incisis cantonibus"; inoltre si edificano "tribus turribus", cioè tre torri, di cui una presumibilmente svolgente le funzioni di mastio. Scomparsa la dominazione sveva in Sicilia, nel 1273 Carlo d'Angiò instituisce una commissione d'inchiesta riguardo allo stato dei castelli nell'isola. Il dominatore giunge a Lentini il 12 aprile del medesimo anno e in questa occasione si redige un documento ufficiale, che descrive le condizioni della fortezza, nonché evidenzia l'esistenza di alcune parti del complesso, non presenti nell'epistola di Federico II: soprattutto si ricorda la presenza di un piccolo edificio sacro all'interno del "Castellaccio". Allo stato attuale degli studi resti di una cappella potrebbero identificarsi con una struttura quadrangolare absidata esistente presso il lato settentrionale del castrum. Alla lista dei castelli fa immediatamente seguito, nel maggio 1274, la composizione dello statuto dei castelli siciliani presso Barletta, rinnovato successivamente nell'agosto del 1281 presso Montefiascone. L'analisi dei due documenti evidenzia un rafforzamento della guarnigione, risultante più che raddoppiata, di stanza all'interno del castrum. Che gli angioini temessero una rivolta? Meno di un anno dopo, il 5 aprile 1282, scoppiano i Vespri Siciliani: Lentini si unisce alla ribellione; il governatore della città, l'angioino Papirio Comitini, si rifugia nel castellaccio, ove è presto raggiunto dalla furia del popolo. Alla fine del medesimo anno è Pietro d'Aragona a sostare presso Lentini per tre giorni.