Zu den bedeutendsten erhaltenen Basiliken der Insel gehört die Kirche Agia Sophia in Panormos. Obwohl die Einweihung des Tempels nicht bekannt ist, hat die Überlieferung den Namen „Agia Sophia“ sowohl für den Tempel als auch für den Ort, an dem er steht, bewahrt. Die Basilika wurde zwischen 1947 und 1955 von K. Kalokiri und N. Plato ausgegraben. Den Ausgräbern zufolge war sie Sitz der Diözese Eleftherni, die nach der Zerstörung der antiken Stadt nach Panormos verlegt wurde. Der ursprüngliche Tempel wurde Ende des 5. Jahrhunderts erbaut, während im 6. Jahrhundert Baumaßnahmen in zwei Phasen durchgeführt wurden.
Der Tempel verfügt über eine reiche und wichtige Skulpturendekoration, Säulen, Kapitelle und Giebel. Sie wurde im Stil einer dreischiffigen Basilika mit Holzdach und einem markanten T-förmigen Querschiff erbaut. Die drei Kirchenschiffe des Tempels waren durch hohe Pilaster mit Säulen mit Kapitellen im korinthischen Stil aus dem 5.-6. Jahrhundert voneinander getrennt. Auf ihnen ruhten die Säulen des ionischen Bogens.
Der Mittelgang war breiter und endete in einem großen Halbkreisbogen, in dem Spuren einer Symphonie sichtbar waren. Im Bereich südlich der Heiligen Treppe (Pastoforio) befindet sich ein späterer Backsteinbau, der als Schwimmbad gilt.
Die Böden der Seitenschiffe waren im Nord- und Mittelschiff gepflastert, im Süden aus verdichteter Erde. Im Westen gibt es einen Narthex und ein Atrium, in dessen Mitte sich ein großer Tank befindet. Nördlich und westlich gibt es mehrere Überreste, deren Verwendung nicht ganz klar ist. Trotz der Zerstörung, die der Tempel während der arabischen Invasionen im 7. Jahrhundert erlitt, deuten die Entdeckung von Münzen von Leo VI. (886 – 912) und die Inschriften mikroschriftlicher Schrift auf Pessos und Schilden darauf hin, dass der Raum bis zum 9. Jahrhundert genutzt wurde.
