Il Palazzo della Zisa risale al XII secolo e fu costruito in epoca normanna. Guglielmo I, detto il Malo, voleva una residenza appena fuori dalla città in cui trascorrere le calde giornate estive, ma Guglielmo morì e il Palazzo fu terminato sotto il regno di suo figlio, Guglielmo II, detto il Buono.
La storia della Zisa è legata a una leggenda che ancora oggi incuriosisce i palermitani. Si narra di un giovane di nome Azel Comel, il cui aspetto riusciva a conquistare tutte le fanciulle. Il giovane si innamorò un giorno di una ragazza molto affascinante, El-Aziz. Il padre di Azel, sultano della Libia, si oppose al matrimonio dei due giovani e allora Azel decise di scappare con la sua amata e il tesoro del padre.
Arrivato a Palermo, fece costruire un palazzo nel cui sotterraneo nascose il tesoro, fatto poi sparire con un incantesimo. Un giorno un uccello viaggiatore consegnò un biglietto a El-Aziz in cui c’era scritto che la madre si stava suicidando a causa del dolore che la partenza della figlia aveva provocato. Quando El-Aziz apprese la notizia, fu colta da grande dispiacere e anche lei si uccise. Azel Comel non riusciva a darsi pace per la perdita della donna amata e iniziò a vagare da un posto all’altro tormentandosi fino a quando, durante un viaggio in nave, morì.
Il tesoro che Azel Comel nascose nel palazzo non fu mai trovato e secondo la leggenda è protetto dai diavoli della Zisa. I Diavoli sono raffigurati sull’arco d’ingresso alla Sala della Fontana, ma nessuno riesce a contarli e pare che il 25 marzo, giorno dell’Annunciazione, si muovano facendo strane smorfie. Chi riuscirà a contare l’esatto numero dei diavoli potrà spezzare l’incantesimo ed entrare in possesso del tesoro.
Da questa leggenda si è diffuso tra i palermitani il detto e che sono, i diavoli della Zisa? che si esclama quando i conti non tornano.