C'est d'abord un fort punique au VII siècle av. J.-C. dont on peut encore apercevoir des vestiges de maçonnerie.
La place forte est conquise par les Romains en -254.
Bélisaire s’en empare en 535 et la ville reste sous la domination byzantine pendant trois siècles.
Les Arabes en font la résidence des Émirs (Qasr) en 831 après leur conquête de la ville.
En 1072, lors de la conquête normande, la forteresse devient le palais des Normands qui la transforment et l'embellissent.
En 1130, Roger II de Sicile, roi de Sicile, décide de faire construire la tour Gjoaria (des joyaux), subdivisée en deux portiques voûtés à quatre arcades (du type des églises byzantines ) qui soutiennent deux salles à déambulatoires : la Salle des Vents et la Salle de Roger, et surtout la chapelle Palatine dédiée à saint Pierre.
Frédéric II de Sicile fonde dans le Palais l’École poétique sicilienne entre 1220 et 1230.
Après l’expulsion des Angevins en 1282, Pierre III d'Aragon s'installe dans le Palais.
Les vice-rois l'habite épisodiquement ensuite.
Après 1500 il subit de grands travaux de restaurations (démolition de tours normandes, édification de cours intérieures: cour Maqueda et cour de la fontaine) jusqu’à l’expulsion des Bourbons, en 1799.
Depuis la fin de la Seconde Guerre mondiale, le palais abrite l'Assemblée Régionale Sicilienne.