La prima Chiesa è costruita nell'attuale area a poche centinaia di metri dal primitivo insediamento Fenicio - Punico dove adesso sorge il Palazzo dei Normanni, lo stesso luogo deputato durante il I, II e III secolo al sacrificio dei primi martiri palermitani oggetto di persecuzioni cristiane. Del luogo di culto edificato intorno al IV secolo e in seguito distrutto dai Vandali, non sono pervenute testimonianze.

Un secondo tempio in epoca bizantina dedicato alla Vergine Maria Assunta è riedificato sulle rovine del precedente nel 604 del quale è pervenuto, la cripta, la pianta basilicale a forma quadrata. Con l'invasione dell'isola da parte dei Saraceni, nel lungo contesto della dominazione araba che a Palermo spazia dall'anno 831 al 1072, la Basilica è trasformata in Moschea. Il ritorno alla sovranità di matrice cristiana e cattolica avviene con l'avvento dei Normanni grazie al contributo congiunto del Gran Conte Ruggero e di Roberto il Guiscardo.

Nel 1184 - 1185 è completata la ricostruzione della nuova cattedrale, voluta dall'Arcivescovo Gualtiero Offamilio. La chiesa fu modificata ancora più volte, ma lo sviluppo in pianta della nuova cattedrale risentì sempre dei forti influssi religioso-architettonici precedenti.

Ripetutamente rimaneggiata e riedificata per svariati eventi, risente anche di interventi dovuti a fenomeni sismici, soprattutto nell'alta torre campanaria sul Palazzo Arcivescovile. Essa viene infatti rifatta nel 1726, su progetto dell'architetto Giovanni Amico in seguito al terremoto di quell'anno, e dal 1826 al 1835, dall'architetto Emmanuele Palazzotto per i danni conseguenti al terremoto del 1823.

La chiesa, felice espressione di molteplici stili, ha subito nel corso dei secoli vari rimaneggiamenti, a volte discutibili. L'ultimo più poderoso è stato effettuato alla fine del Settecento, quando, in occasione del consolidamento strutturale, si rifece radicalmente l'interno su progetto di Ferdinando Fuga. Nel 1767 infatti, l'arcivescovo Serafino Filangieri aveva commissionato a Ferdinando Fuga un restauro conservativo dell'edificio, teso solamente a consolidarne la struttura. I lavori ebbero inizio solo dal 1781, eseguiti non dal Fuga ma dal palermitano Carlo Chenchi con l'assistenza di Giuseppe Venanzio Marvuglia e durarono fino al XIX secolo inoltrato. I rifacimenti furono in realtà molto più invasivi e radicali dei progetti dell'architetto fiorentino, che, secondo alcuni studiosi, pensava invece di conservare, almeno in parte, il complesso longitudinale delle navate e l'originario soffitto ligneo. Il restauro intervenne a cambiare l'aspetto originario del complesso, dotando la chiesa della caratteristica ma discordante cupola, eseguita secondo i disegni del Fuga. Fu in quest'occasione che si distrusse la preziosa tribuna che Antonello Gagini aveva innalzato dal 1510 e che era ornata di statue, fregi e rilievi. Anche le pittoresche cupolette maiolicate destinate alla copertura delle navate laterali risalgono al rifacimento del 1781. In questa cattedrale, sintesi di storia e di arte dell'ultimo millennio in Sicilia, oltre ai sovrani normanni, svevi, catalani, sono stati incoronati Vittorio Amedeo II di Savoia e Carlo III di Borbone.

L'interno, che ha subito profonde trasformazioni tra la fine del Settecento e i primi dell’Ottocento, è a croce latina con tre navate divise da pilastri (gruppi tetrastili con 4 colonne incastonate provenienti dalla antica costruzione rogeriana) con statue di santi che facevano parte della decorazione della tribuna del Gagini.

Nella navata destra, la prima e la seconda cappella, comunicanti fra di loro, custodiscono le tombe imperiali e reali dei normanni, intorno alle quali ruota una storia romanzesca e ricca d'interesse. Ruggero II, re dal 1130, aveva stabilito già nel 1145 che il Duomo di Cefalù da lui fondato diventasse il mausoleo della famiglia reale. In tal senso aveva predisposto la sistemazione di due sarcofagi in porfido, un granito molto prezioso e di notevole durezza, originario dell'Egitto, dal colore rosso cupo che, nell'antichità, era usato esclusivamente per le commissioni imperiali. Alla sua morte nel 1154, però, egli venne sepolto nella cattedrale di Palermo in un avello di porfido dalla forma molto più semplice. Nel 1215 Federico II fece trasportare i due sarcofagi da Cefalù alla cattedrale di Palermo destinandoli a sé e al padre Enrico VI. Il sarcofago di Federico II è sormontato da un baldacchino con colonne in porfido e l'urna è sorretta da due coppie di leoni; insieme a quelli di Federico II sono stati conservati anche i resti di Pietro II d’Aragona. Le altre tombe sono quelle di Costanza d'Aragona (1183-1222), sorella del re d'Aragona e moglie di Federico II, di Guglielmo, duca d'Atene figlio di Federico III di Sicilia, e dell'imperatrice Costanza d'Altavilla, figlia di Ruggero II e madre di Federico II.

Sul pavimento della navata centrale è stata realizzata, durante i rifacimenti moderni, una meridiana in marmo con tarsie colorate che rappresentano i segni zodiacali, (opera di Giuseppe Piazzi, astronomo, qui collocata nell'anno 1801). Il ricco altare del Sacramento, in bronzo, lapislazzulo e marmi colorati, è stato realizzata su disegno di Cosimo Fanzago(XVII secolo). Nel presbiterio si dispone il bellissimo coro ligneo tardo-quattrocentesco in stile gotico-catalano e il trono episcopale, ricomposto in parte con frammenti d'antichi mosaici del XII secolo. Durante la fase dei restauri della fine del XVIII secolo, fu incaricato il pittore di Sciacca Mariano Rossi di decorare la cattedrale. Gli affreschi, secondo il disegno originale, dovevano ricoprire il catino dell'abside, la volta del coro, la cupola e la navata centrale, e dovevano rappresentare idealmente il ristabilimento della religione cristiana in Sicilia ad opera dei Normanni. Mariano Rossi iniziò nel 1802 e non terminò tutto il lavoro, ma ancora oggi si possono ammirare gli affreschi nel catino dell'abside, dove sono rappresentati Roberto il Guiscardo e il conte Ruggero che restituiscono la chiesa al vescovo Nicodemo e nella volta del coro, dove è dipinta l'Assunzione di Maria Vergine.