Μετά τη διοικητική διαίρεση της Ρωμαϊκής Αυτοκρατορίας το 395 μ.Χ., η Κρήτη εντάχθηκε στην Ανατολική Ρωμαϊκή Αυτοκρατορία, η οποία αργότερα έγινε γνωστή ως Βυζαντινή. Η βυζαντινή παρουσία στο νησί διαιρείται σε δύο περιόδους: την Πρώτη Βυζαντινή Περίοδο, από το 395 έως την αραβική κατάκτηση του 824–827, και τη Δεύτερη Βυζαντινή Περίοδο, από την ανακατάληψη του 961 έως την κατάλυση της αυτοκρατορικής κυριαρχίας μετά την Τέταρτη Σταυροφορία το 1204.

Η Πρώτη Βυζαντινή Περίοδος

Κατά την Πρώτη Βυζαντινή Περίοδο η Κρήτη διατήρησε σε μεγάλο βαθμό τη διοικητική και αστική οργάνωση των ύστερων ρωμαϊκών χρόνων. Η Γόρτυνα παρέμεινε πρωτεύουσα και σημαντικότερο διοικητικό και εκκλησιαστικό κέντρο του νησιού. Ο χριστιανισμός, που είχε ήδη διαδοθεί κατά τους προηγούμενους αιώνες, εδραιώθηκε πλήρως, οργανώθηκαν επισκοπές και ανεγέρθηκαν πολυάριθμοι ναοί.

Ανάμεσα στα σημαντικότερα μνημεία της περιόδου συγκαταλέγεται η μεγάλη παλαιοχριστιανική βασιλική του Αγίου Τίτου κοντά στη Γόρτυνα. Σημαντικά κατάλοιπα έχουν επίσης αποκαλυφθεί στην παλαιοχριστιανική βασιλική στο Καστρί Χερσονήσου, στη βασιλική της Αγίας Σοφίας στο Πάνορμο, στη βασιλική της Αλμυρίδας, στη Σούγια και σε πολλές ακόμη παράκτιες και ηπειρωτικές θέσεις.

Οι μεγάλες βασιλικές, τα ψηφιδωτά δάπεδα, τα βαπτιστήρια και τα υπόλοιπα εκκλησιαστικά κτίρια μαρτυρούν όχι μόνο την εξάπλωση του Χριστιανισμού αλλά και την οικονομική δραστηριότητα των πόλεων. Παράλληλα, αρκετά από τα παλαιότερα αστικά κέντρα άρχισαν σταδιακά να συρρικνώνονται, καθώς σεισμοί, επιδημίες, οικονομικές μεταβολές και επιδρομές επηρέασαν τη ζωή του νησιού.

Το Εμιράτο της Κρήτης

Η Πρώτη Βυζαντινή Περίοδος έληξε όταν Ανδαλουσιανοί μουσουλμάνοι εξόριστοι, οι οποίοι είχαν προηγουμένως εγκατασταθεί στην Αίγυπτο, κατέλαβαν σταδιακά το νησί μεταξύ 824 και 827. Ίδρυσαν το Εμιράτο της Κρήτης και δημιούργησαν ως πρωτεύουσά του τον οχυρωμένο Χάνδακα, στη θέση του σημερινού Ηρακλείου. Παρά τις επανειλημμένες βυζαντινές εκστρατείες, η αραβική κυριαρχία διατηρήθηκε για περισσότερο από έναν αιώνα.

Η Δεύτερη Βυζαντινή Περίοδος

Το 960 ξεκίνησε μια μεγάλη εκστρατεία υπό τον στρατηγό και μετέπειτα αυτοκράτορα Νικηφόρο Φωκά. Ο βυζαντινός στρατός αποβιβάστηκε στην Κρήτη και πολιόρκησε τον ισχυρά οχυρωμένο Χάνδακα. Η πόλη καταλήφθηκε τον Μάρτιο του 961 και το νησί εντάχθηκε ξανά στη Βυζαντινή Αυτοκρατορία.

Κατά τη Δεύτερη Βυζαντινή Περίοδο αναδιοργανώθηκαν η διοίκηση, η άμυνα και η εκκλησιαστική ζωή της Κρήτης. Οι επισκοπές αποκαταστάθηκαν, ιδρύθηκαν ή ανακαινίστηκαν ναοί και μοναστήρια και ενισχύθηκαν οι οχυρώσεις σημαντικών πόλεων και στρατηγικών θέσεων. Στρατιώτες, κληρικοί και οικογένειες από άλλες περιοχές της αυτοκρατορίας εγκαταστάθηκαν στο νησί, συμβάλλοντας στην οικονομική και πληθυσμιακή του ανασυγκρότηση.

Χαρακτηριστικό μνημείο αυτής της περιόδου είναι το Βυζαντινό Τείχος των Χανίων, το οποίο περιέβαλλε τον λόφο Καστέλι, στην ακρόπολη της αρχαίας Κυδωνίας. Αντίστοιχα οχυρωματικά έργα δημιουργήθηκαν ή ενισχύθηκαν και σε άλλες περιοχές, καθώς η προστασία από θαλάσσιες επιδρομές αποτελούσε βασική προτεραιότητα.

Η βυζαντινή κυριαρχία τερματίστηκε ουσιαστικά μετά την κατάληψη της Κωνσταντινούπολης από την Τέταρτη Σταυροφορία το 1204. Τα δικαιώματα κυριαρχίας στην Κρήτη παραχωρήθηκαν αρχικά στον Βονιφάτιο τον Μομφερρατικό, ο οποίος τα μεταβίβασε στη Δημοκρατία της Βενετίας. Ακολούθησε σύγκρουση με τους Γενουάτες και οι Ενετοί άρχισαν να εγκαθιστούν την εξουσία τους στο νησί το 1211, εγκαινιάζοντας μια νέα περίοδο στην ιστορία της Κρήτης.