La sua fondazione, piuttosto incerta, è da collocarsi prima dell'invasione araba se è vero che questi usarono la cattedrale come "vilissima stalla". A causa di questa frequentazione "infedele" il Duomo fu nuovamente consacrato nel 1192 alla presenza dell'Arcivescovo Berzio, dell'imperatore Enrico VI (figlio del Barbarossa) e della moglie Costanza d'Altavilla.
La prima delle tante disavventure che segnano la storia del Duomo avvenne nel 1254 durante i funerali di Corrado IV, figlio di Federico II di Svevia: un incendio provocò la distruzione del tetto ligneo realizzato da artigiani arabi.
Dal 1300 si susseguono una serie di modifiche che se da una parte arricchiscono artisticamente la cattedrale (mosaici delle absidi, portale, facciata), dall'altra snaturano l'originario aspetto normanno. In seguito, danneggiato dai terremoti del 1638 e del 1783 che rovinò buona parte della facciata, fu quasi interamente distrutto da quello del 28 dicembre 1908.
Il sisma risparmiò soltanto la parte absidale e riportò alla luce molti elementi della primitiva costruzione normanna. La ricostruzione degli anni 20 ripristinò l'aspetto originario recuperando gran parte delle opere d'arte e dei mosaici.
La seconda guerra mondiale diede un altro duro colpo alla millenaria struttura, forse il peggiore: il 13 giugno del 1943 un grappolo di bombe caduto sul Duomo causò un terribile incendio che distrusse irrimediabilmente gran parte dell'interno. La struttura attuale che si è voluta il più possibile vicino all'originale mantiene nell'esterno pregevoli parti dal XIV al XVII secolo. Da segnalare in particolare la facciata con il magnifico portale in stile gotico e le belle finestre quattrocentesche sulla parete di destra della cattedrale (il portale del lato destro è attribuito a Polidoro da Caravaggio).
Nell'interno, tripartito da una doppia fila di 13 colonne con arcate ogivali, si possono ammirare mosaici (sec. XIV e rifacimenti), alcuni monumenti funebri, tra cui quello di Guidotto de Tabiatis arcivescovo di Messina nel XIV secolo ed alcune statue di santi, in particolare il S. Giovanni Battista di Antonello Gagini del 1525.