Byens rødder borer ned i oldtiden, da de første folk bosatte sig på bjerget, nok netop på grund af det gode udsyn over hele området, som gjorde det muligt let at forsvare sig.

I VII-VI århundrede f. Kr. kom byen under græsk indflydelse, og dens betydning voksede, eftersom den var det vigtigste kultsted for Demeter.

Henna, som den dengang hed, var dog, ud over denne rigdom af myter og legender, også en frodig egn, som tiltrak mere verdslige interesser. At besidde denne by betød ikke blot at dominere Sicilien komplet og ubestridt, men også at nyde produkterne af denne usædvanligt frugtbare jord.

Hver ny hersker på Sicilien måtte for at opnå den fulde magt lægge sig ud med fjenden, som sad i denne befæstede by, og ofte var en sejr kun mulig ved list. Således var det, da araberne trængte ind i byen takket være en byzantinsk spion, og også da det lykkedes for normannerne efter en længere belejring fra 1061 endelig at indtage byen i 1088.

Efter det arabiske herredømme, blev Henna under normannerne til Castrogiovanni (fra det arabiske navn Qasr-Jannih, som igen kom af det latinske Castrum Hennae) og berigedes op igennem middelalderen med de kirker og monumenter, som eksisterer endnu i dag.