An der östlichen Küste der Halbinsel Spinalonga, in der Bucht von Kolokytha, befindet sich eine weitere Basilika, die laut oberflächlichen Hinweisen in direktem Zusammenhang mit bewohntem Gebiet und dem Betrieb des dortigen Hafens steht.

Der Tempel hat mindestens zwei Bauphasen. Die erste stammt aus dem 5. Jahrhundert, während die zweite in der Zeit von Kaiser Justinian im mittleren 6. Jahrhundert n. Chr. stattfand, als das ursprüngliche Holzdach der Basilika durch Gewölbe und eine zentrale Kuppel ersetzt wurde. In der zweiten Phase wurde der Tempel mit reichhaltigem Marmorschmuck aus Prokonnesos verziert, der in den Werkstätten von Konstantinopel hergestellt wurde.

Basierend auf der Münzzeugnis wird die Nutzung der Basilika bis zum 7. Jahrhundert n. Chr. belegt.