Alla cripta, risalente al X secolo, si accede per mezzo di una scalinata sotto l’altare maggiore. Essa è preceduta da un vestibolo alla cui estremità è addossato un altare: sotto di esso la sepoltura dell’Arcivescovo Ferdinando Bernardi, mentre sopra esso è collocato un bassorilievo rinascimentale in stucco raffigurante la Madonna con il Bambino, opera di scuola fiorentina del secondo Quattrocento. Il succorpo è costituito da tre bracci (il quarto braccio è stato probabilmente distrutto durante la costruzione della cattedrale normanna) ed è coperto da volte a crociera a sesto rialzato su tozze colonne di reimpiego con capitelli a lastra, che suddividono la cripta in navate. Le colonne risultano tozze perché senza dubbio il livello originario di calpestio era molto più besso di quello attuale.
Nel braccio centrale della cripta, sulla parete di destra si possono ammirare gli affreschi risalenti quasi sicuramente alla prima metà del 1400, anche se alcuni critici li collocano nel 1200. Si tratta di un trittico a palinsesto raffigurante iniziando da sinistra San Cataldo, la Maddalena e San Zosimo che somministra la comunione a Santa Maria Egiziaca. Altri resti di affreschi sono sparsi sulle superfici murarie di tutta la cripta. Degno di nota è il sarcofago in marmo del XIII secolo: sul fronte un altorilievo scolpito raffigurante due angeli con dei ceri in una mano e con l’altra reggono le braccia di un’anima in atteggiamento orante. Si tratta sicuramente della sepoltura di una bambina.