La piccola chiesa di San Cataldo sorge accanto alla Martorana su un terrazzo che la pone in posizione dominante. Poche sono le notizie storiche: l'edificio fu sicuramente di proprietà di Majone da Bari, Ammiraglio e Cancelliere del re Guglielmo I, tra il 1154 ed il 1160 ma non si sa se ne fu anche il costruttore. Scomparsi gli adiacenti edifici che costituivano il palazzo signorile, la chiesa conserva intatte le sue forme.

L'interno è diviso in tre navate da sei colonne. La navata centrale è costituita da tre campate a pianta quadrata coperte da cupole. Sulle campate orientali si innestano le tre absidi poco profonde. Caratteristica di questa come di altre chiese palermitane è la fusione della componente centrica data dalle cupole con la componente basilicale. La chiesa conserva il pavimento cosmatesco e l'altare originali. Il secondo è costituito da una lastra di marmo decorata a sottile incisione con un Agnus Dei circondato dai simboli degli evangelisti.

Adiacente la chiesa sul lato via Maqueda si possono ancora vedere le antiche mura di epoca romana della città. Dal 3 luglio 2015 fa parte del Patrimonio dell'umanità (Unesco) nell'ambito dell'"Itinerario Arabo-Normanno di Palermo, Cefalù e Monreale".