Κατά την πρώτη βυζαντινή περίοδο (330-824), με τη μεταφορά της πρωτεύουσας του Ρωμαϊκού κράτους στο Βυζάντιο και την ίδρυση της Κωνσταντινούπολης το 330 μ.Χ., η Κρήτη περιήλθε στο Ανατολικό ρωμαϊκό κράτος και αποτέλεσε ξεχωριστή επαρχία με διοικητή Βυζαντινό στρατηγό. Από εκεί και στο εξής άρχισε να εξαπλώνεται στο νησί ο χριστιανισμός και τον 8ο αι. μ. Χ η επισκοπή της Κρήτης περιήλθε στο Πατριαρχείο της Κωνσταντινούπολης. Κατά τα παλαιοχριστιανικά και πρωτοβυζαντινά χρόνια ανεγέρθηκαν στο νησί πολλοί ναοί, αρκετούς από τους οποίους έχει φέρει στο φως η αρχαιολογική έρευνα.
Από το 824 μ.Χ. έως το 961 μ.Χ. επικρατεί Αραβοκρατία στο νησί γεγονός που στο Ρέθυμνο επιβεβαιώνεται από ελάχιστες μαρτυρίες ανάμεσα στις οποίες και ορισμένα αραβικά νομίσματα που βρέθηκαν στο χωριό Γιαννούδη.
Στη δεύτερη Βυζαντινή περίοδο (961-1210) πραγματοποιείται όπως θα δούμε και παρακάτω η πρώτη οχύρωση της πόλης τους Ρεθύμνου και από το 1211 ξεκινά η μακρά και πολύ ενδιαφέρουσα περίοδος της Βενετοκρατίας τα σημάδια της οποίας σε όλα τα επίπεδα ανιχνεύονται άριστα στην περιοχή της πόλης του Ρεθύμνου