Come dimostrato da un diploma greco-arabo del 1143, da un'iscrizione greca all'esterno della facciata meridionale e dalla stessa raffigurazione musiva di dedicazione, la chiesa fu fondata nel 1143 per volere di Giorgio d'Antiochia, il grande ammiraglio siriaco al servizio del re normanno Ruggero II dal 1108 al 1151, e fu dedicata alla Madonna: motivo per il quale diventò nota come "Santa Maria dell'Ammiraglio". All'edificio sacro, che nel corso dei secoli è stato più volte distrutto e restaurato, si accede dal campanile: una costruzione a pianta quadrata del XIII secolo, aperta in basso da arcate arcuate a colonne angolari e con tre grandi ordini di grandi bifore.La chiesa possiede una pianta a croce greca, prolungata con il nartece e l'atrio. Un portale assiale (ancora esistente) da sull'atrio e il nartece, come nelle prime chiese cristiane. Al di là del nartece, l'edificio era sistemato e decorato come una chiesa bizantina a 4 colonne, tranne gli archi a sesto acuto e i pennacchi della cupola che erano di origine islamica. Nel 1193 le case attorno vengono adibite a Convento basiliano per le donne e la chiesa verrà poi ad esso inglobata. Attorno al 1394 avviene la fondazione del convento della Martorana (dal nome dei proprietari) che sarà ceduto ai Benedettini dalla corona normanna e che darà poi il nome alla chiesa. Negli anni 1683-87, l'abside centrale viene distrutta e sostituita da una nuova abside rettangolare, progettata da Paolo Amato. Nel 1740 Nicolò Palma progetta un nuovo prospetto, secondo il gusto barocco dell'epoca, che si affaccia sulla piazza. Nel 1846 si realizza l'abbassamento del piano della piazza e viene realizzata la scalinata.
Nel 1870-73 Giuseppe Patricolo ne realizza il drastico restauro. Stacca i marmi settecenteschi delle pareti laterali del presbiterio (di cui era prevista la distruzione) e accenna il muro di chiusura originale.
Entrati nel primo corpo della costruzione - rifacimento settecentesco con volte affrescate da Olivio Sozzi, Antonio Grano e Guglielmo Borremans - due decorazioni musive sul fronte del corpo originario raffigurano Ruggero II e Giorgio d'Antiochia; solo la testa e le mani di quest'ultimo sono originali dell'epoca.
Superato l'ambiente suddetto, si giunge nella chiesa vera e propria. Qui la parte superiore delle pareti e la cupola, al sommo della quale è l'immagine del Cristo Pantocratore, sono interamente rivestite di decorazioni musive di periodo bizantino, le più antiche di tutta la Sicilia e di grande importanza, in connessione con quelle riguardanti Dafne, nell'Attica.
I mosaici della cupola rappresentano al centro il Cristo, poi scendendo si vedono i 4 arcangeli (tre originali più uno apocrifo) e i patriarchi, mentre nelle nicchie sono ospitati i quattro evangelisti e infine, nelle volte, i rimanenti apostoli.L'abside, distrutta sul finire del Seicento, venne sostituita con l'attuale cappella barocca a tarsie marmoree.
I dolci a base di marzapane e per lo più a forma di frutta devono il nome di "martorana" al fatto che a prepararli e a venderli erano fino al XIX secolo le suore del monastero della Martorana. Da qui l'espressione "frutta di Martorana".

La frutta martorana

La frutta di martorana o pasta reale, uno dei dolci più tipici della pasticceria siciliana, deve il nome all'omonima chiesa. La tradizione risale al Medioevo, quando ogni convento si specializzava nella confezione di un particolare tipo di dolce. All'inizio di novembre, per la ricorrenza dei morti, il convento benedettino della Martorana preparava questi dolcetti di marzapane, lavorati e colorati in modo da assumere le sembianze di frutta vera. Ancora oggi durante la Fiera dei Morti la zona tra via Spicuzza e piazza Olivella è invasa di bancarelle coloratissime che offrono frutta martorana, pupi di zucchero e giocattoli per i bambini.
Il marzapane ha un'origine medievale: il nome deriva infatti dall'arabo mauthaban che in origine designava una moneta, poi un'unità di misura e infine il contenitore in cui veniva conservata questa pasta a base di mandorle, zucchero e albume d'uovo.