Der früheste architektonische Stil des byzantinischen Kirchenbaues geht auf die ersten Jahre des Byzantinerreiches zurück (4. bis 6. Jahrhundert n. Chr.). Man nennt solche Kirchen "dreischiffige Basilika(Trikliti Vasiliki), weil sie längsseits in drei Flügel unterteilt sind, wobei der rechteckige Bau meist doppelt so lang wie breit war. Das Mittelschiff (Klitos) ist vielfach breiter und höher als die Seitenschiffe und sorgt mit seinen Fenstern für den Lichteinlass. Oft hatte jedes Schiff seine eigene Eingangstüre. Bögen und Marmorsäulen, gern mit verzierten Kapitellen (Kionokrana) trennten die Schiffe voneinander. Für den Boden wurden Mosaike mit einfachen Darstellungen bevorzugt. Der Priester hatte seinen Platz am Kopf des Mittelschiffes gegenüber dem Haupteingang. Bisweilen hatte die Kirche am Kopf noch ein viertes Schiff im rechten Winkel zu den drei anderen. Andere Bauten wiederum verfügten über einen zusätzlichen Flügel am Eingang, ebenfalls im rechten Winkel zu den anderen drei Schiffen. Dieser sogenannte Prothalamos oder Narthex war der Platz, wo ungetaufte Personen dem Gottesdienst beiwohnen konnten.

Die Überreste von mehr als 40 Basiliken wurden auf Kreta gefunden. Zu den ältesten dreischiffigen Basiliken zählt die Panagia Paliani in Venerato, die bereits im Jahre 668 n. Chr. als "Palai(alt) bezeichnet wurde. An mehreren Stellen sieht man noch Kapitelle von den Marmorsäulen früherer Bauten. Eine andere alte Basilika mit antiken Marmorsäulen ist die Kirche des Agios Pandeleimon in Bizariano (Pigi, Pediada). Mosaikböden mit Darstellungen von Fischen gibt es in Elounda und mit Vögelbildern in Sougia (Selino). Die dreischiffige Basilika des Agios Ioannis in Lithino (Pediada) hatte einen Raum (Narthex) direkt am Eingang im rechten Winkel zu den drei Hauptschiffen. Die Überreste einer anderen Basilika in Panormon (Milopotamos) hat das vierte Schiff am Kopfende der Kirche gegenüber dem Eingang. Dieses zusätzliche Schiff ragt rechts und links über die anderen drei Flügel heraus, so daß der ganze Bau die Form eines T hat. There are remains of ancient basilicas in Vizari, Amari and Itanos, Sitia.