Le prime notizie indicanti il 1165 come data d’inizio della costruzione della Zisa, sotto il regno di Guglielmo I, ci sono state tramandate da Ugo Falcando nel Liber de Regno Siciliae. Sappiamo da questa fonte che nel 1166, anno della morte di Guglielmo I, la maggior parte del palazzo era stata costruita “mira celeritate, non sine magnis sumptibus” (lett. "con straordinaria velocità, non senza ingenti spese) e che l’opera fu portata a termine dal suo successore Guglielmo II (1172-1184), subito dopo la sua maggiore età. L’appellativo Mustaʿizz è riferito, secondo Michele Amari, a Guglielmo II anche in un’iscrizione in caratteri naskhī nell’intradosso dell’arcata d’accesso alla Sala della Fontana.

Un’altra iscrizione, invece, ben più famosa – in caratteri cufici – è a tutt’oggi conservata nel muretto d’attico del palazzo, tagliata ad intervalli regolari nel tardo medioevo, quando la struttura fu trasformata in fortezza. Alla luce di queste fonti, la maggior parte degli studiosi sono concordi nel fissare al 1175 la data di completamento dei lavori del solarium reale. Fino al XVII secolo il palatium non venne sostanzialmente modificato, come ci testimonia la descrizione del 1526 fatta dal monaco bolognese Leandro Alberti, che visitò la Zisa in quell’anno. Significativi interventi di restauro si ebbero negli anni 1635-36, quando Giovanni de Sandoval acquistò la Zisa, adattandola alle nuove esigenze abitative. In occasione di questi lavori fu aggiunto un altro piano chiudendo il terrazzo e si costruì, nell’ala destra del palazzo, secondo la moda dei tempi, un grande scalone, resecando i muri portanti e distruggendo le originarie scale d’accesso.

Successivamente nel 1806 la Zisa passò alla famiglia dei Notabartolo, che effettuò diverse opere di consolidamento, quali il risarcimento di lesioni sui muri e l’incatenamento degli stessi per contenere le spinte delle volte. Venne trasformata la distribuzione degli ambienti mediante la costruzione di tramezzi, soppalchi, scalette interne e nel 1860 fu ricoperta la volta del secondo piano per costruire il pavimento del padiglione ricavato sulla terrazza. Nel 1955 il palazzo fu espropriato dallo Stato, ed i lavori di restauro, iniziati immediatamente, vennero poco dopo sospesi. Dopo un quindicennio d’incuria ed abbandono nel 1971 l’ala destra, compromessa strutturalmente dai lavori del Sandoval e dagli interventi di restauro, crollò. Attualmente la Zisa ospita il Museo della civiltà islamica.