Η πρώτη περίοδος Βυζαντινής διακυβέρνησης διάρκεσε από το 395 μ.Χ. μέχρι το 824 μ.Χ.. Κατά τη διάρκεια αυτής της περιόδου η Κρήτη υπήρξε τμήμα της Βυζαντινής Αυτοκρατορίας, η οποία είχε πρωτεύουσά της την Κωνσταντινούπολη. Έγινε ξεχωριστή επαρχία της Αυτοκρατορίας και την κυβερνούσε ένας Βυζαντινός Στρατηγός, γεγονός που της επέτρεψε να συμμετέχει στο χτίσιμο της Ελληνικής Βυζαντινής Αυτοκρατορίας. Ο Χριστιανισμός εξαπλώθηκε και εδραιώθηκε στο νησί. Χτίστηκαν μάλιστα υπέροχες εκκλησίες, κυρίως βασιλικές. Υπάρχουν ερείπια από 40 τουλάχιστον βασιλικές αυτής της περιόδου. Οι πιο σημαντικές απ' αυτές βρίσκονται στη Γόρτυνα, την Ίτανο, τη Χερσόνησο, τη Σούγια, τη Πάνορμο, την Ελούντα και τη Μητρόπολη.