Η εκκλησία της Κρήτης κατά την πρωτοβυζαντινή περίοδο ήταν μια από τις δώδεκα  αρχιεπισκοπές της επαρχίας του Ιλλυρικού που υπάγονταν στον θρόνο της Ρώμης. Μετά το 476, όταν η Ρώμη κυριεύτηκε από τους Βησιγότθους, η εκκλησία της Κρήτης προσαρτήθηκε για μικρό χρονικό διάστημα στο Πατριαρχείο της Κωνσταντινούπολης, για να επανέλθει στην δικαιοδοσία του Πάπα μετά την ανάκτηση της Ιταλίας από τον Ιουστινιανό. Το εκκλησιαστικό αυτό καθεστώς διατηρήθηκε ως το 731/2 μ.Χ. όταν ολόκληρη η επαρχία του Ιλλυρικού πέρασε από την παπική δικαιοδοσία στο Πατριαρχείο της Κωνσταντινούπολης.

Ο Μουσώνιος, επίσκοπος Ἡρακλείας καταγράφεται ανάμεσα στους κρητικούς επισκόπους στα Πρακτικά της Συνόδου της Σαρδικής το 343/344 μ.Χ. Ο ίδιος επίσκοπος υπογράφει την επιστολή προς τον Άγιο Αθανάσιο μαζί με άλλους τρεις κρητικούς επισκόπους. Ένας επίσκοπος Ἡρακλειουπόλεως συμμετείχε, μαζί με άλλους κρητικούς ιεράρχες, στη Σύνοδο της Νίκαιας το 787 μ.Χ. Η γειτνίαση του Ηρακλείου με την επισκοπή Κνωσού, γνωστή ήδη από το 170μ.Χ., και οι παραλλαγές του ονόματος (Ηράκλεια, Ηρακλειούπολις) στα εκκλησιαστικά έγγραφα, έκαναν πολλούς μελετητές να απορρίψουν την ταύτιση του Ηρακλείου με την έδρα της επισκοπής. Ωστόσο η ταύτιση δύσκολα αμφισβητείται, καθώς ο επίσκοπος υπογράφει ανάμεσα στους Κρήτες επισκόπους Λάμπης και Κνωσού. Δυστυχώς, μέχρι το 731/2 μ.Χ. οι επίσκοποι Κρήτης δεν καταγράφονταν στους καταλόγους του Πατριαρχείου της Κωνσταντινούπολης. Πληροφορίες αντλούνται μόνο από τα Πρακτικά των Συνόδων, στα οποία παρατηρούνται συχνά λάθη στα ονόματα των εδρών, λόγω της συμμετοχής εκατοντάδων επισκόπων. Ίσως η αναγόρευση του Ηρακλείου σε επισκοπή, σε μικρή απόσταση από αυτή της Κνωσού να οφείλεται στο γεγονός ότι αποτελούσε τη γενέτειρα πόλη του Ευάρεστου, ενός από τους Αγίους Δέκα Μάρτυρες, που μαζί με τον Ζωτικό από την Κνωσό μαρτύρησαν στη Γόρτυνα κατά τη διάρκεια του διωγμού του Δεκίου το 249 μ.Χ. Σύμφωνα με την Επιστολή των Κρητών επισκόπων στον αυτοκράτορα Λέοντα Α΄ το 457 μ.Χ., οι Άγιοι Δέκα Μάρτυρες θεωρούνταν πάτρονες της Κρητικής Εκκλησίας.