A parte le leggende legate alla Cattedrale, di cui rimandiamo alla pagina, la Cattedrale di Cefalù, dal carattere di fortezza, venne iniziata nel 1131, per volontà di Ruggero II, ma probabilmente mai finita. La prima pietra fu posta il giorno di Pentecoste di quell’anno, alla presenza del vescovo Ugone arcivescovo di Messina (la ricostituita Diocesi di Cefalù ne era suffraganea). Sappiamo che nel 1145 fu messo mano, da parte di manodopera bizantina, ai bellissimi mosaici dell’abside. Questi raffigurano il Cristo Pantocratore (dal greco pantocrator, "sovrano di tutte le cose") nell'atto di benedire con le tre dita della mano destra, tipico dell'uso ortodosso. In effetti la raffigurazione è legata alla cultura bizantina, ma la incontriamo anche in quella paleocristiana e medievale in genere. La troviamo, ad esempio, nella Basilica di Santa Sofia a Costantinopoli (che poi fu trasformata dai turchi in moschea, nel 1453, e oggi è un museo per volere di Ataturk), ma anche nelle stesse icone del rito ortodosso. La raffigurazione del Cristo Pantocratore è oggi presente in Sicilia, oltre alla Cattedrale di Cefalù, anche in quella di Monreale e nella cappella Palatina del Palazzo dei Normanni di Palermo. In Italia altri esempi si possono ammirare nelle chiese di Ravenna (la chiesa di San Vitale), nel Duomo di Cremona, nella Cattedrale di Pisa, il Battistero di Firenze e nell'abbazia di Novalesa a Torino.
Nella Cattedrale di Cefalù furono anche collocati, nella navata trasversale della basilica, i sarcofagi porfiretici. Questi , secondo la volontà di Ruggero II, avrebbero dovuto essere l’ultima sua dimora e della moglie. Comprovano questo diversi elementi che possiamo vedere tutt’oggi: raffigurazioni in rilievo del leone (emblema di regalità), la tartaruga (simbolo di eternità), Edipo cieco (metafora degli enigmi della vita), e il Profeta Elia innalzato in cielo dai capelli dell'angelo. Tuttavia la Storia ha voluto che fossero spostati (e, infatti, non si trovano più nella Cattedrale). Per ordine di Federico II, "approfittando dell'assenza temporanea dell'allora vescovo di Cefalù Jocelmo", furono trasferiti a Palermo, loro sede attuale.
Fa parte del complesso della Cattedrale anche un raffinato chiostro annesso, che presenta colonne binate con capitelli figurati sovrapposti, preziosiosissimo esempio di scultura medievale in Sicilia.