La edificarono i normanni nel 1184, come rinnovata chiesa cristiana, sul luogo di una precedente basilica trasformata in moschea dagli arabi. Dal sec. XIV subì numerose manomissioni, che lasciarono tuttavia inalterate le originarie strutture fino alla radicale trasformazione del 1781-1801 quando, su progetto di Ferdinando Fuga, si modificò l'interno e si aggiunse la cupola. La facciata principale conserva l'aspetto del sec. XIV-XV con due torri a bifore e colonnine, arcate cieche, coronamento orizzontale e un portale gotico (prima metà del sec. XV) sormontato da una bifora (nell'edicola, Madonna quattrocentesca). Due archi ogivali congiungono la facciata alla torre campanaria, medievale nel massicio volume inferiore, sormontato da una serie di campanili rifatti 'in stile' nell'800. Sul fianco sinistro della Cattedrale è un portico gaginesco della metà del '500, inglobato nella ristrutturazione tardosettecentesca. All'inizio del fianco destro avanza tra due torrette un ampio portico a tre alte arcate ogivali, esempio di gotico fiorito catalaneggiante, eretto nel 1429-30: sulla prima colonna a sinistra, probabilmente già nella chiesa al tempo dagli arabi, è inciso un passo del Corano; si noti il portale con battenti lignei del 1432, sormontato da un mosaico della fine del sec. XIII. La parte absidale*, che conserva le forme del sec. XII, s'incurva in tre absidi, percorse da un motivo ad archi intrecciati. L'interno, trasformato in forme neoclassiche tra il 1781 e il 1801, è a tre navate su pilastri (addossate a questi, statue di santi di Antonello Gagini, già parte di una scomposta tribuna) con cupola e profondo presbiterio. Navata destra: la 1ª e 2ª cappella custodiscono le celebri tombe imperiali e reali*, con urne di porfido, di maestosa semplicità; in primo piano, al muro di destra, un sarcofago romano con scena di caccia è la tomba di Costanza d'Aragona; a destra la tomba di Enrico VI, a sinistra quella di Federico II; in secondo piano, a destra la tomba dell'imperatrice Costanza, a sinistra quella di Ruggero II. La cappella a destra del presbiterio, cappella di S. Rosalia, custodisce l'urna argentea (1631) con le reliquie della santa, patrona della città. Da notare anche il ricco coro ligneo gotico-catalano del 1466. La cripta a due navate su colonne (sec. XII) presenta sette absidiole con sarcofagi di varie epoche. Il Tesoro della Cattedrale comprende preziosi oggetti di oreficeria, smalti, codici miniati e paramenti sacri; di particolare interesse la tiara in oro di Costanza d'Aragona, moglie di Federico II, con smalti, gemme e perle.