L'antica chiesa fu eretta dall'arcivescovo Gualtiero di Offamil, parente di Ruggero, dal 1170 al 1194, secondo lo stile gotico, che il duomo ha ancora conservato, nonostante le molte ed infelici mutazioni a cui andò soggetto. Dell'antica chiesa non lasciò che la cappella di S. Maria Incoronata, nella quale furono incoronati Ruggero e tutti i suoi successori, come accenna l'iscrizione hic regi corona datur. Nel 1781 il duomo fu restaurato, o per dir meglio fu deturpato, per opera dell'architetto napoletano Ferdinando Fuga, il quale eresse una barocca cupola e fece molti altri lavori che ne alterarono completamente l'antico stile. Però, nonostante questi non felici restauri, il duomo di Palermo produce ancora una grande impressione, perchè riunisce in sè la semplicità dell'architettura gotica, e la grazia degli archi e degli arabeschi saraceni, e non v'è altro edificio a Palermo che mostri con tanta evidenza i contrasti di cui è ricca la storia dell'isola.
Il duomo sorge libero, su una piazza di discreta ampiezza, circondata da una balaustra con barocche statue. In mezzo, sopra un piedistallo triangolare s'innalza la statua di S. Rosalia, protettrice della città; questa santa è per i Palermitani quello che per i Napoletani è S. Gennaro.
Ai quattro angoli del duomo si levano quattro torri e sopra le navate laterali delle piccole cupole. L'antico campanile quadrato, per fortuna, non fu restaurato; secondo l'uso toscano sorge accanto alla chiesa ed è a questa unito per mezzo di archi. La tribuna, di forma semicircolare, è ornata con arabeschi in nero. Sulle pareti esteriori, nelle porte, nelle finestre, nelle fasce, nelle cornici si vedono graziose sculture dalle forme fantastiche di colonne e di merli. Sulle porte sta il maggiore ornamento; soprattutto sono da ammirarsi i ricchi arabeschi della porta maggiore e lo stile della porta laterale. Il portico, del 1430, è formato da tre archi a sesto acuto, i quali riposano sopra quattro colonne. Sulle pareti interne dell'altro si vedono due sculture moderne, rappresentanti l'incoronazione di Carlo III e di Vittorio Amedeo di Sardegna, che fu per pochi anni re di Sicilia.
L'interno della chiesa, interamente rimodernata, appare semplice e di piacevole aspetto; ha tre navate a forma di croce latina, con archi a sesto tondo, sostenuti da pilastri. Le cappelle e gli altari sono sopraccarichi di ornati di gusto assai barocco. V'abbondano il marmo e il porfido, ma non vi sono sculture, nè pitture di pregio, eccezione fatta di due acquasantiere di marmo, una delle quali appartiene alla scuola di Antonio Gagini, discepolo di Michelangelo ed uno dei migliori scultori della Sicilia. Nel duomo ci sono pure molte opere di questo chiaro artista, mirabili sopratutto alcuni monumenti sepolcrali nella cripta sotterranea, edificata al tempo dei Normanni e conservante tutto il suo antico carattere di basilica ad archi a sesto acuto sostenuti da gigantesche colonne di granito. Lungo le pareti si allineano le tombe degli arcivescovi di Palermo, consistenti per la maggior parte in sarcofaghi di mediocre lavoro romano. L'aspetto semplice e severo di questo edificio produce una profonda impressione.
La cosa però più pregevole del duomo sono le tombe dei re della stirpe normanna, e di quella degli Hohenstaufen: monumenti non solo della storia siciliana, ma anche di quella tedesca. Queste tombe sono collocate in una cappella della navata di destra; sono dei sarcofaghi di puro e severo stile, di porfido rosso cupo o di marmo. Non ho visto mai nessuna tomba dei tempi cristiani che abbia un carattere così semplice e severo come queste, e che sembri come queste fatta per durare eternamente. Gli stessi due sarcofaghi di porfido del tempo di Costantino, che si ammirano in Vaticano, non producono un'eguale impressione, perchè i loro bassorilievi distraggono alquanto l'attenzione. Tombe di una così grandiosa semplicità e di una maestà così severa potrebbero servire anche per i re dei Nibelungi. In esse si riconosce l'impronta grandiosa del secolo XIII. Attestano che in quell'epoca i Siciliani avevano conservata l'arte di lavorare il porfido, arte che nel resto della penisola era andata perduta e non fu ritrovata, narra il Vasari, che alla metà del secolo XVI da Francesco del Todda.
In queste tombe sono sepolti il gran re Ruggero, Costanza sua figlia, il marito di lei Arrigo VI, Federico II, il principe più geniale che abbia avuto la Germania, e la sua prima moglie Costanza d'Aragona.
La tomba di Federico è quella che più colpisce la nostra attenzione. Egli morì a Firenzuola, presso Luceria, nelle Puglie, il 13 dicembre 1250, in età di soli cinquantasei anni; e la sua salma fu trasportata in Sicilia da sei squadroni di cavalleria e dalle guardie saracene, e venne deposta nella stessa chiesa dove aveva da ragazzo ricevuta la corona e dove aveva fatto incoronare suo figlio Manfredi. Questi aveva incaricato Arnolfo di Lapo, discepolo dell'illustre Nicola Pisano, d'innalzare uno stupendo monumento all'imperatore suo padre, che però non fu eseguito. Non si sa bene chi sia stato l'autore del monumento attuale, se un Toscano od un Siciliano. Il sarcofago, col coperchio ornato di aquile e di grifoni, posa sopra quattro leoni, i quali tengono fra le loro zanne degli schiavi; al di sopra si erige un tempietto, sostenuto da colonne.
Nel 1491 il vicerè spagnuolo Ferdinando di Acunta si arrischiò ad aprire quelle tombe: alla presenza degli arcivescovi di Palermo e di Messina e del Senato Palermitano, fece scoperchiare i sarcofaghi di Arrigo VI e di Costanza di Aragona, e, solo per la disapprovazione manifesta di tutti gli astanti, si trattenne dall'aprire anche le altre tombe. Quando nel 1781 il duomo fu restaurato, le tombe che si trovavano in una cappella di fianco al coro, vennero trasportate dove ora si vedono, e in quella occasione vennero tutte aperte. Il principe di Torremuzza, che si trovò presente, l'11 agosto, alla loro apertura, narra nella sua vita: «I cadaveri di Ruggero I, di Arrigo VI e di Costanza si trovarono quasi completamente distrutti e nulla di notevole si potè osservare nei loro ornamenti; invece, le salme di Federico II e di Costanza II, suscitarono grande ammirazione per la ricchezza dei loro abbigliamenti e per la qualità delle gemme che insieme con i due principi erano state sepolte. Sulla corona di Arrigo VI e sulla camicia che Federico II portava sotto le altre sue vesti, si trovarono ricamati parecchi caratteri arabi, che furono esattamente ricopiati e spediti, per mio suggerimento, al professore Tichsen, in Butzow, per averne la traduzione».
Le parole del principe non concordano esattamente con la notizia pubblicata dallo storiografo napoletano Daniele, intitolata: I sepolcri del duomo di Palermo illustrati. Secondo questa, il cadavere di Federico II si sarebbe trovato rivestito di magnifici abiti, quantunque con poco decoro si fossero collocati nella stessa tomba due altri cadaveri, uno dei quali fu ritenuto per Pietro II di Aragona, morto nel 1342. La corona dell'imperatore, ornata di perle, posava sopra un guanciale di cuoio, ed a sinistra del suo capo stava lo scettro. Portava in dito un anello con uno smeraldo; al suo fianco stava la spada; aveva attorno al corpo una cintura di seta, con fibbie d'argento; era calzato con stivali di seta, ricamati a colori, ed aveva speroni d'oro.
Disgraziatamente, di questo gran principe non ci è pervenuto nessun ritratto autentico; non possediamo che quelli delle sue monete, e quello, scolpito in un anello, che lo storico Daniele fece incidere con l'aiuto di una maschera in gesso di Federico. Gli abitanti di Capua avevano eretto sul ponte del Volturno una statua all'imperatore Federico e a' suoi due consiglieri, Taddeo di Sessa e Pier della Vigna; oggi rimane solo la statua dell'imperatore ed in assai cattivo stato, perchè, secondo quanto narra Raumer, una soldatesca sfrenata le ruppe le braccia e i piedi e ne buttò a terra la testa. Prima che la statua fosse così mutilata, Daniele aveva preso l'impronta della fisonomia e con questa aveva inciso l'anello.