Τον 6ο αι. ο πάπας Γρηγόριος Α΄ οικοδόμησε εδώ μία βασιλική. Τον 9ο αι. οι Σαρακηνοί κατέλαβαν την πόλη και μετέτρεψαν τη βασιλική σε τζαμί. Όταν οι Νορμανδοί κατέλαβαν τη Σικελία, ο Βάλτερ Οφάμιλ (Βάλτερ του Μύλου), Αγγλο-Νορμανδός αρχιεπίσκοπος του Παλέρμο και υπουργός του Γουλιέλμου Β΄ της Σικελίας, έκτισε στη θέση του τζαμιού το 1185 τον τωρινό ναό. Το μεσαιωνικό αρχικό οικοδόμημα ήταν βασιλική, που τα τρία κλίτη της απέληγαν ανατολικά σε τρία ημιθόλια, αλλά από αυτά μόνο λίγα αρχιτεκτονικά στοιχεία επέζησαν ως την εποχή μας. Το 1191 απεβίωσε ο Βάλτερ και τάφηκε σε σαρκοφάγο στην κρύπτη του ναού.

Το επάνω μέρος των δύο γωνιαίων πύργων φτιάχτηκε τον 14ο και 15ο αι. Κατά την πρώιμη Αναγέννηση φτιάχτηκε το νότιο προστώο, που τροποποιήθηκε το διάστημα 1781-1801 σε νεοκλασικό ρυθμό με την επίβλεψη του Φερντινάνντο Φούγκα. Κατά την περίοδο αυτή καταστράφηκε η εικόνα του βωμού (retable) του Αντονέλλο Γκατζίνι, που ήταν διακοσμημένη με αγάλματα, ανάγλυφα και μία διακοσμητική ζώνη· τα γλυπτά μεταφέρθηκαν σε διαφορετικά μέρη της βασιλικής. Ο Φούγκα πρόσθεσε έναν μεγάλο τρούλο στο κεντρικό κλίτος και μικρότερους στο πλαϊνά κλίτη.