Die Kirche wurde von Georg von Antiochien, dem Ammiratus König Rogers II. von Sizilien, gestiftet und ab 1143 erbaut. Sie erfuhr im Lauf der Geschichte zahlreiche bauliche Veränderungen. Ursprünglich war sie über dem Grundriss eines griechischen Kreuzes in quadratischer Form errichtet. Bis in das 13. Jahrhundert tagte im Atrium der Kirche der städtische Gerichtshof. 1435 wurde die Kirche an das Benediktinerinnenkloster der Eloisia Martorana angegliedert. Daher hat sie auch ihren Beinamen.

Ab 1588 erhielt die Kirche durch Einbeziehung des ursprünglichen Atriums in den Bau eine längliche Form. Bei diesem Umbau wurde auch die mittlere Apsis eingerissen und zu einem rechteckigen Altarraum erweitert. Im 17. Jahrhundert wurde dem ehemaligen Atrium eine Barockfassade zur Piazza Bellini hin vorgesetzt. Bei einer Restaurierung im 19. Jahrhundert wurde teilweise der mittelalterliche Zustand wiederhergestellt.

Der Glockenturm, der auf der der Kirche gegenüberliegenden Seite an das Atrium errichtet wurde, seit dem Umbau des 16. Jahrhunderts jedoch direkt an die Westfassade der Kirche anschließt, ist in seinen unteren zwei Stockwerken noch im Originalzustand erhalten. Die oberen Stockwerke sind im 14. Jahrhundert im Stil der katalanischen Gotik hinzugefügt worden.

Seit 1943 ist La Martorana Sitz der Pfarrei San Nicolò dei Greci mit byzantinischem Ritus für alle in Palermo wohnenden italo-griechischen Gläubigen und Konkathedrale der Eparchie Piana degli Albanesi.