L'edificazione ebbe inizio nel 1131 e nei decenni seguenti furono realizzati i mosaici nell'abside e sistemati i sarcofagi porfiretici che Ruggero II aveva destinato alla sepoltura sua e della moglie. Federico II trasferì a Palermo i due sarcofagi reali nel 1215, riutilizzandoli per sé e per i suoi familiari. Nel Quattrocento tra le due torri fu inserito un portico a tre fornici, opera di Ambrogio da Como.

La decorazione musiva, forse prevista per tutto l'interno, fu realizzata solamente nel presbiterio e ricopre attualmente l'abside e circa la metà delle pareti laterali. I mosaici coprono una superficie di oltre 600 m² e furono realizzati entro il 1148 (prima fase) e poi probabilmente tra il 1154 e il 1166. I più antichi sono quelli dell'abside e della crociera e furono iniziati probabilmente nel 1145; per la loro realizzazione, Ruggero II chiamò maestri bizantini, di Costantinopoli, che adattarono ad uno spazio architettonico per loro anomalo, di tradizione nordica, cicli decorativi di matrice orientale.

Della decorazione pittorica rimangono una figura di Urbano V, della fine del XIV secolo, dipinta su una colonna della navata di sinistra, ed una Madonna in trono del XV secolo nel braccio sinistro del transetto. All'interno il duomo ospita alcuni monumenti funerari, tra cui un sarcofago tardo antico, un altro medievale e il pregevole sepolcro del vescovo Castelli, opera dello scultore Leonardo Pennino (XVIII secolo).

Il fonte battesimale, ricavato da un unico grande blocco di lumachella, è decorato da quattro leoncini scolpiti (XII secolo). È custodita inoltre una statua marmorea di Madonna commissionata alla bottega di Antonello Gagini da Filippo Serio del 1533. Sul basamento è presente la Dormienza di Maria bassorilievo e le effigi del committente e della moglie.

Si conservano ancora due organi dipinti, settecenteschi, che chiudono le navate verso il transetto, e una croce lignea dipinta, opera di Guglielmo da Pesaro (1468 circa).

La cappella del Santissimo Sacramento (protesi) conserva la decorazione a stucco neoclassica, realizzata per tutto l'interno e successivamente asportata altrove. La cappella conserva inoltre un altare d'argento del XVIII secolo, opera di artigiani palermitani.

Il soffitto della navata centrale presenta una decorazione dipinta con busti, animali fantastici e motivi decorativi, opera di maestranze arabe e normanne, e altre di gusto gotico fatte realizzare da Enrico Ventimiglia nel 1243.