Η θέσπιση της αρχής της ανεξιθρησκίας το 313 μ.Χ. με το Διάταγμα των Μεδιολάνων και η σύγκληση της Α΄ Οικουμενικής Συνόδου το 325 μ.Χ. άνοιξαν μια νέα εποχή για τη Χριστιανική Εκκλησία στον τότε γνωστό κόσμο. Η Κρήτη δεν αποτέλεσε εξαίρεση. Από τον 4ο αι. ο Χριστιανισμός άρχισε να επικρατεί στο νησί, όπως φαίνεται από τον κατάλογο των 22 επισκοπών, οι οποίες αναγράφονται στο Συνέκδημο του Ιεροκλέους (Πολιτική Γεωγραφία του Ιεροκλέους του Γραμματικού, 528-535 μ.Χ.). Η Εκκλησία της Κρήτης θα αναλάμβανε στο εξής έναν ενεργό ρόλο στις εκκλησιαστικές προκλήσεις της εποχής και αυτό φαίνεται από τη συμμετοχή της στην Γ΄, Δ΄, Ε΄, ΣΤ΄ και Ζ΄ Οικουμενική Σύνοδο.
Το 457-458 μ.Χ. οι επίσκοποι του νησιού υπέγραψαν ομολογία ορθόδοξης πίστης προς τον αυτοκράτορα Λέοντα Α΄ (457-474 μ.Χ.), ενώ κατά τον επόμενο αιώνα, πιθανόν επί Ιουστινιανού (527-565 μ.Χ.), κτίστηκε στη Γόρτυνα, που αποτελούσε εξαρχής την έδρα της αρχιεπισκοπής, μεγαλοπρεπής βασιλική προς τιμήν του Αποστόλου Τίτου. Σύμφωνα με τα πρακτικά των Συνόδων, η ιεραρχική θέση της Εκκλησίας της Κρήτης στον κατάλογο των Εκκλησιών που συμμετείχαν σ’ αυτές δεν παρέμενε σταθερή. Αρχικά, ο αρχιεπίσκοπος φαίνεται να βρίσκεται ανάμεσα στην 39η και 48η και αργότερα ανάμεσα στην 9η και 14η θέση. Η άνοδος στην ιεραρχική κλίμακα των Εκκλησιών αποδεικνύει εν ολίγοις και τη σημαντική οργανωτική δομή που είχε επιδείξει η τοπική Εκκλησία στο εσωτερικό της. Οι εννέα επισκοπές κατά τον 2ο αι. είχαν αυξηθεί σε 12 και, όπως αναφέρθηκε πιο πριν, έφτασαν τις 22 τον 6ο αι.
Την περίοδο αυτή η Εκκλησία της Κρήτης ήταν στη δικαιοδοσία του πάπα Ρώμης, ως μία από τις δώδεκα Αρχιεπισκοπές του Ιλλυρικού. Μάλιστα, ο πάπας ήταν εκείνος που διόριζε τον βικάριο που τον υποκαθιστούσε στο Ανατολικό Ιλλυρικό. Η πνευματική εποπτεία του παπικού θρόνου επί της Εκκλησίας της Κρήτης ενισχύθηκε το 535 μ.Χ. με διάταγμα του Ιουστινιανού Α' μέχρι το 732-733 μ.Χ., οπότε και η τελευταία θα υπαχθεί στο Οικουμενικό Πατριαρχείο. Αν και η Κρήτη ήταν εκκλησιαστικώς εξαρτημένη από τη Ρώμη, οι σχέσεις της με την Κωνσταντινούπολη ήταν στενές. Αυτό φαίνεται από την εκλογή του Ανδρέα του Ιεροσολυμίτη ως αρχιεπισκόπου Κρήτης, πράξη που τελέστηκε το 710 ή 711 μ.Χ. στην Κωνσταντινούπολη και όχι στην έδρα του πάπα. Διακεκριμένος εκκλησιαστικός ποιητής και υμνογράφος της Ορθόδοξης Εκκλησίας, ο Ανδρέας ο Ιεροσολυμίτης είχε και ως διάκονος χειροτονηθεί στην Πόλη το 685 μ.Χ. Άσκησε μεγάλο φιλανθρωπικό έργο και έγινε ιδιαίτερα γνωστός για τη σύνθεση του Μεγάλου Κανόνα.
Σε γενικές γραμμές, από τον 5ο έως το α΄ μισό του 7ου αι. επικράτησε ειρήνη στο νησί. Ο Χριστιανισμός είχε εδραιωθεί, οι επισκοπές – διάσπαρτες σ’ όλο το νησί- αποτελούσαν το κέντρο της πνευματικής ζωής, μεγάλες εκκλησιαστικές φυσιογνωμίες κρατούσαν τα ηνία της Εκκλησίας και νέοι επιβλητικοί ναοί κτίζονταν διαρκώς. Όμως, επί Λέοντος του Γ΄ (714-741 μ.Χ.), η κατάσταση άλλαξε άρδην, εξαιτίας της διάσπασης των πιστών σε εικονομάχους και εικονολάτρες. Η θεολογική και πολιτική διαμάχη, που ξέσπασε στο Βυζάντιο αναφορικά με τη λατρεία των χριστιανικών εικόνων (726-842 μ.Χ.), προκάλεσε μεγάλη κρίση και στη μεγαλόνησο. Κατά την αυτή περίοδο, σύμφωνα με τη χρονογραφία του Θεοφάνους του Ομολογητή, ένας Κρητικός οπλαρχηγός, ο Κοσμάς, επιτέθηκε στην Κωνσταντινούπολη με στόλο από την Κρήτη και τις Κυκλάδες, συνεπικουρούμενος μάλιστα από τον τουρμάχη (διοικητή) του ελληνικού θέματος, τον Αγαλλιανό. Αν και τα αίτια της εξέγερσης είναι αμφιλεγόμενα, πολλοί ερευνητές θεωρούν την ενέργεια αυτή ως απάντηση στην εικονομαχική πολιτική του αυτοκράτορα. Τελικά, ο στόλος καταστράφηκε με υγρό πυρ ανοικτά της Κωνσταντινούπολης στις 18 Απριλίου του 727 μ.Χ και οι πρωτεργάτες της εξέγερσης εκτελέστηκαν.
Επί Κωνσταντίνου του Ε' (741-775) καταγράφηκαν ακόμη σκληρότερες διώξεις εναντίον των εικονολατρών. Στα χρόνια αυτά, ένας μοναχός, ο Παύλος, εκτελέστηκε από τον διοικητή της Κρήτης Θεοφάνη Λαρδότυρο, ενώ το 767 μ.Χ. μαρτύρησε ο γνωστός για τους αγώνες του κατά της εικονομαχίας, ο Ανδρέας ο εν τη Κρίσει. Ο τελευταίος αποδοκίμασε τον αυτοκράτορα Ε΄ μέσα στον ναό του Αγίου Μάμαντα, με αποτέλεσμα να διαπομπευτεί και να βασανιστεί. Μεταξύ των υπερασπιστών της λατρείας των εικόνων ήταν και ο Νικόλαος ο Στουδίτης, ηγούμενος της ονομαστής Μονής Στουδίου της Κωνσταντινούπολης, που καταγόταν από την Κυδωνία.
Η κρίση της εικονομαχίας ήταν η αιτία που το 732-733 μ.Χ., εξαιτίας της εικονόφιλης πολιτικής του πάπα, η Εκκλησία της Κρήτης αποσπάστηκε από την εκκλησιαστική δικαιοδοσία του και υπήχθη στο Οικουμενικό Πατριαρχείο. Προκαθήμενος της Εκκλησίας ήταν εκείνη την περίοδο ο Ανδρέας ο Ιεροσολυμίτης, ενώ λίγο αργότερα στον αρχιεπισκοπικό θρόνο ανέβηκε ένας εξίσου λόγιος ιεράρχης, ο Ηλίας. Ο Κρήτης Ηλίας έλαβε μέρος στην Ζ΄ Οικουμενική Σύνοδο το 787 μ.Χ. μαζί με έντεκα επισκόπους, τον Λάμπης Επιφάνιο, τον Ηρακλειουπόλεως (Ηρακλείου) Θεόδωρο, τον Κνωσού Αναστάσιο, τον Κυδωνίας Μελίτωνα, τον Κισάμου Λέοντα, τον Σουρβίτων Θεόδωρο, τον Φοίνικος Λέοντα, τον Αρκαδίας Ιωάννη, τον Ελευθέρνης Επιφάνιο, τον Καντάνου Φωτεινό και τον Χερρονήσου Σισίνιο. Λίγες δεκαετίες αργότερα η Κρήτη έπεφτε στα χέρια των Αράβων. Μια νέα και συνάμα σκοτεινή περίοδος ξεκινούσε για την Εκκλησία και το ποίμνιό της, που έπρεπε να επιβιώσει κάτω από το ζυγό του αλλόθρησκου κατακτητή.