В центре Палермо, примерно в 700 метрах восточнее кафедрального собора, на площади Беллини находится церковь Святого Катальда. Рядом с ней расположена ещё одна церковь – Марторана. Некоторые документы говорят о связи этой церкви с Майо из Бари – министром короля норманнов Вильгельма I и его главного адмирала, на здании церкви есть надпись с упоминанием дочери этого человека. Исследователи предполагают, что здание церкви было возведено из песчаника примерно в 1154 году, и, несомненно, арабами для христианских заказчиков. Вильгельм II в 1182 году передал её монреальским монахам-бенедектинцам, которые владели церковью до 1787 года. Позднее тут расположилась почта.
Джузеппе Патриколо в 1882-85 годах реконструировал здание, вернув ему изначальный арабо-норманнский облик: арабский фриз с резными зубцами, орнамент из слепых арок, красные купола характерной полусферической формы с оконцами. В наши дни храмом владеет орден Гроба Господня.
План церкви имеет прямоугольную форму, изнутри здание разделено на три недлинных нефа. Центральный неф разделяется колоннами в соответствии с ритмическим рисунком куполов. Арки свода поддерживают колонны, капители которых взяты от более поздних строений. Интерес представляет древний главный алтарь и мозаичный пол с неплохой сохранностью. Мозаики в прошлом украшали и стены здания, но до наших дней они не сохранились.