Nach der administrativen Teilung des Römischen Reiches im Jahr 395 wurde Kreta Teil des Oströmischen Reiches, das später als Byzantinisches Reich bekannt wurde. Die byzantinische Herrschaft auf der Insel gliedert sich in zwei Abschnitte: die erste byzantinische Epoche von 395 bis zur arabischen Eroberung in den Jahren 824–827 und die zweite byzantinische Epoche von der Rückeroberung im Jahr 961 bis zum Zusammenbruch der kaiserlichen Herrschaft nach dem Vierten Kreuzzug von 1204.

Die erste byzantinische Epoche

Während der ersten byzantinischen Epoche behielt Kreta weitgehend die Verwaltungs- und Stadtstrukturen der spätrömischen Zeit. Gortyn blieb die Hauptstadt und das bedeutendste Verwaltungs- und Kirchenzentrum der Insel. Das Christentum, das sich bereits in den vorausgegangenen Jahrhunderten verbreitet hatte, festigte sich endgültig. Bistümer wurden organisiert und zahlreiche Kirchen errichtet.

Zu den wichtigsten Denkmälern dieser Zeit gehört die große frühchristliche Basilika des heiligen Titus bei Gortyn. Bedeutende Überreste frühchristlicher Kirchen wurden außerdem in Hersonissos, Panormo, Sougia, Almyrida, Eleftherna und an zahlreichen weiteren Orten entdeckt. Auch im Gebiet des antiken Olous bei Elounda sind Reste einer bedeutenden frühchristlichen Basilika erhalten.

Große Basiliken, Mosaikfußböden, Taufkapellen und weitere kirchliche Gebäude bezeugen nicht nur die Verbreitung des Christentums, sondern auch die wirtschaftliche Tätigkeit der damaligen Städte. Gleichzeitig schrumpften mehrere ältere urbane Zentren allmählich, da Erdbeben, Epidemien, wirtschaftliche Veränderungen und Überfälle das Leben auf der Insel beeinträchtigten.

Das Emirat von Kreta

Die erste byzantinische Epoche endete, als muslimische Verbannte aus Al-Andalus, die sich zuvor in Ägypten niedergelassen hatten, Kreta zwischen 824 und 827 schrittweise eroberten. Sie gründeten das Emirat von Kreta und machten das befestigte Chandax, an der Stelle des heutigen Heraklion, zu ihrer Hauptstadt. Trotz wiederholter byzantinischer Feldzüge blieb die Insel mehr als ein Jahrhundert unter arabischer Herrschaft.

Die zweite byzantinische Epoche

Im Jahr 960 begann unter dem Feldherrn und späteren Kaiser Nikephoros Phokas ein großer Feldzug. Das byzantinische Heer landete auf Kreta und belagerte die stark befestigte Stadt Chandax. Im März 961 wurde die Stadt erobert und die Insel erneut in das Byzantinische Reich eingegliedert.

Während der zweiten byzantinischen Epoche wurden die Verwaltung, das Verteidigungssystem und das kirchliche Leben der Insel neu organisiert. Bistümer wurden wiederhergestellt, Kirchen und Klöster gegründet oder erneuert und die Befestigungen wichtiger Städte und strategischer Plätze verstärkt. Soldaten, Geistliche und Familien aus anderen Teilen des Reiches ließen sich auf Kreta nieder und trugen zur wirtschaftlichen und demografischen Erholung der Insel bei.

In Chania wurde der Kastelli-Hügel, die Akropolis des antiken Kydonia, mit einer starken Mauer befestigt, von der noch heute Teile erhalten sind. Ähnliche Verteidigungsanlagen entstanden oder wurden auch in anderen Regionen verstärkt, da der Schutz vor Angriffen vom Meer weiterhin eine zentrale Aufgabe darstellte.

Die byzantinische Herrschaft endete faktisch nach der Eroberung Konstantinopels durch den Vierten Kreuzzug im Jahr 1204. Die Herrschaftsrechte über Kreta wurden zunächst Bonifatius von Montferrat zugesprochen, der sie an die Republik Venedig übertrug. Anschließend kam es zu Auseinandersetzungen mit den Genuesen. Ab 1211 begannen die Venezianer, ihre Herrschaft auf der Insel durchzusetzen, womit ein neuer Abschnitt der kretischen Geschichte einsetzte.