Panagia significa "Santísima", pero la etimología de Ekatontapyliani no está clara; pues aunque hekaton significa "cien" y pylaion "puerta" (obviamente, no tiene cien puertas), se ha propuesto que proviene de la palabra Katapoliani ("la parte baja de la ciudad"), en referencia a su situación topográfica.
Su construcción se remonta al año 326, lo que la convierte en una de las primeras iglesias del cristianismo primitivo.
También existe una versión en la que se atribuye a Justiniano I la fundación.
La parte más antigua es la capilla de San Nicolás y el baptisterio (siglo IV -época paleocristiana-).
Hay numerosos mosaicos bizantinos de los siglos VI y VII.