Nel 1550 vengono avviati i lavori per costruire una fortificazione sulla Meta, pianura in collina sopra Lentini, ordinati dal Viceré Giovanni De Vega. Nel 1551 nasce Carleontina con privilegio di "cità" e con l'epiteto di "Inespugnabile". 
Per evitare il deperimento della fortificazione, il Viceré si adopera per popolarla stabilmente. A coloro che si trasferiscono nella città concede particolari diritti, come privilegi fiscali, moratorie sui debiti, esenzione dal servizio militare e dall'obbligo di dare vitto e alloggio agli ufficiali di passaggio. Il 17 settembre 1559 il Tribunale Patrimoniale di Messina rende esecutivi i 20 capitoli contenenti i diritti e i privilegi della città, riconosciuta come cesarea, demaniale e fortificata, con autonomia amministrativa. 
Fin dalla nascita, Carleontina entra in contrasto con Lentini: nel 1551 ottiene lo spostamento della fiera d'aprile dalla città concorrente. Questa tornerà a Lentini nel 1559, solo dopo che Carleontina viene autorizzata a tenere la fiera di S. Matteo. 
Dalla nascita fino al 1630 gli avvenimenti più significativi sono: un incendio, nel 1561, di origine sconosciuta, che devasta la città e l'elezione, il 15 marzo 1621, a Patrona, Protettrice ed Avvocata della città della vergine e martire siracusana Santa Lucia.