330μ.Χ.-1204 μ.Χ.
Το 330 η Κρήτη απελευθερώνεται από τους Ρωμαίους και προσαρτάται στη Βυζαντινή Αυτοκρατορία. Γίνεται «Θέμα», αυτοτελή δηλαδή διοικητική περιφέρεια, και ορίζεται ως στρατιωτική και διοικητική έδρα του νησιού η Γόρτυνα. Η διοίκηση ανατέθηκε σε βυζαντινό στρατηγό, ο οποίος κλήθηκε ν’ αντιμετωπίσει τις επιδρομές των πειρατών που είχαν επιφέρει σημαντικές καταστροφές στην οικονομία του νησιού.
Κατά τη βυζαντινή περίοδο η Κυδωνία διατήρησε τη σπουδαία θέση που διατηρούσε στην Κρήτη και παρακολουθούσε από κοντά όλες τις εξελίξεις σε εκκλησιαστικό κυρίως επίπεδο. Ήδη από τα πρώτα χριστιανικά χρόνια είχε ιδρυθεί η επισκοπή Κυδωνίας, ο επίσκοπος της οποίας συμμετείχε μαζί με άλλους επισκόπους του νησιού στη Σύνοδο της Σαρδικής (Σόφιας) στα 342-343. Εκκλησιαστικά υπαγόταν στη δικαιοδοσία του μητροπολίτη Γορτύνης και από τα τέλη του 9ου αιώνα στο μητροπολίτη του Χάνδακα (Ηράκλειο).
Όσον αφορά το χώρο εγκατάστασης του μητροπολιτικού ναού, η αρχαιολογική έρευνα εντόπισε κατάλοιπα μιας μεγάλης παλαιοχριστιανικής βασιλικής στη θέση του βενετσιάνικου καθεδρικού ναού της Παναγίας, στο κέντρο του λόφου Καστέλι. Πιθανόν ο ναός αυτός να αποτελούσε την επισκοπή Κυδωνίας.
Τον 7ο αιώνα για να προστατέψουν τα Χανιά από τους Σαρακηνούς, οι Βυζαντινοί θα οχυρώσουν το λόφο του Καστελίου με το λεγόμενο «βυζαντινό τείχος», θα σκάψουν μία τάφρο και θα κατασκευάσουν και ένα προτείχισμα γύρω από το λόφο μετατρέποντας το ουσιαστικά σε νησί.
Δυστυχώς, οι όποιες ενέργειες δεν στάθηκαν ικανές να εμποδίσουν την επίθεση των Αράβων. Οι Σαρακηνοί κατέλαβαν την Κρήτη το 824 και το 828 η Κυδωνία καταστράφηκε. Η περίοδος της Αραβοκρατίας (824-961) υπήρξε οδυνηρή για ολόκληρο το νησί, καθώς αυτό μετατράπηκε σε ορμητήριο ληστρικών και πειρατικών επιδρομών. Οι αρχαιολογικές ενδείξεις για τα χρόνια αυτά είναι ελάχιστες, γνωρίζουμε όμως ότι τη περίοδο αυτή ζούσε ο Όσιος Νικόλαος Στουδίτης, ο οποίος γεννήθηκε στην Κυδωνία το 793 και σε ηλικία 10 ετών εγκαταστάθηκε στην Κωνσταντινούπολη.
Το 961 οι Βυζαντινοί ανακαταλαμβάνουν την Κρήτη και η πόλη αρχίζει και πάλι να διαδραματίζει το σπουδαίο οικονομικό και εμπορικό της ρόλο λόγω του λιμανιού, αν και είναι πιθανή η προσπάθεια μεταφοράς της σε πιο ασφαλή χώρο και συγκεκριμένα στο νέο φρούριο “Κάστελλος”, που κτίζεται κοντά στο Βαρύπετρο. Την περίοδο αυτή μεταφέρεται η έδρα της επισκοπής από τα Χανιά στην Αγιά και ο βυζαντινός ναός της Κοιμήσεως της Θεοτόκου μετατρέπεται σε καθεδρικό ναό της Κυδωνίας.
Οι Βυζαντινοί είχαν ως κύριο μέλημα την επαναφορά της οικονομικής, κοινωνικής και θρησκευτικής ηρεμίας στο νησί. Γι’ αυτό και μετέφεραν από την Κωνσταντινούπολη αρχοντικές οικογένειες, τα «Δώδεκα Αρχοντόπουλα», ενώ παρότρυναν την ανοικοδόμηση πολλών εκκλησιών. Μεταξύ αυτών ήταν και η μονή του Αγίου Ιωάννου του Θεολόγου πάνω στα ερείπια της αρχαίας Απτέρας.
