Οι ρίζες της Ορθόδοξης Εκκλησίας της Κρήτης πηγάζουν απευθείας από την αποστολική παράδοση. Πρώτοι κήρυκες του Χριστιανισμού στο νησί ήταν οι Εβραίοι της Κρήτης, οι οποίοι, σύμφωνα με τις πράξεις των Αποστόλων (β', 11), παραβρέθηκαν στα Ιεροσόλυμα στο κήρυγμα του Πέτρου την ημέρα της Πεντηκοστής, το 33 μ.Χ., και πίστεψαν στο Χριστιανισμό. Ο συστηματικός ωστόσο εκχριστιανισμός και η αρχική οργάνωση της τοπικής Εκκλησίας στο νησί συνδέονται με τις περιοδείες του Αποστόλου Παύλου και ιδιαίτερα με την τοποθέτηση του μαθητή και συνεργάτη του, Αποστόλου Τίτου, ως πρώτου επισκόπου.
Οι περισσότεροι ερευνητές τοποθετούν την επίσημη ίδρυση της εκκλησίας στην περίοδο που ακολουθεί τα πρώτα δεσμά του Αποστόλου Παύλου στη Ρώμη (62-63 μ.Χ.), κατά την οποία πραγματοποίησε την Δ΄ ιεραποστολική περιοδεία του. Λίγο νωρίτερα, το 60-61 μ.Χ., είχε ξανάρθει στην Κρήτη, όταν το πλοίο που τον μετέφερε στη Ρώμη αναγκάστηκε να προσορμίσει στους Καλούς Λιμένες, στη νότια πλευρά του νησιού (Πραξ. κζ΄ 8). Ο τόπος λοιπόν ήταν ήδη γνώριμος, ωστόσο, λόγω των πολλών υποχρεώσεων του, ο Παύλος δεν μπορούσε να παραμείνει στο νησί. Όπως φαίνεται από την επιστολή που έστειλε λίγο μετά στον Τίτο «Τούτου χάριν καπέλιπόν σε εν Κρήτη, ίνα τα λείποντα επιδιορθώσης και καταστήσης κατά πόλιν πρεσβυτέρους, ως εγώ σοι διεταξάμην» (Τιτ. 1,5), ο τελευταίος ανέλαβε το δύσκολο έργο της ιεραποστολής. Εκτός από μία σειρά οργανωτικών ζητημάτων που έπρεπε να επιλύσει για τη στερέωση της νεοϊδρυθείσας εκκλησίας, είχε να αντιμετωπίσει και προβλήματα που δημιουργούσαν οι διάφοροι ψευδοδιδάσκαλοι και ειδωλολάτρες που δεν έβλεπαν με καλό μάτι την ανάπτυξη των πρώτων χριστιανικών κοινοτήτων. Αυτή ήταν και η αιτία που ο Παύλος συνέγραψε την επιστολή προς τον Τίτο, δίνοντάς του οδηγίες για τη διαποίμανση των χριστιανικών κοινοτήτων του νησιού απέναντι στις κάθε είδους ετεροδοξίες.
Με επισκοπική έδρα τη Γόρτυνα, που αποτελούσε και το διοικητικό κέντρο του νησιού, ο Τίτος, ως πρώτος επίσκοπος, κήρυξε το ευαγγέλιο και ίδρυσε εκκλησίες στις μεγαλύτερες πόλεις του νησιού, χειροτονώντας επισκόπους και πρεσβυτέρους. Κοιμήθηκε γύρω στο 105 μ.Χ., αφού είχε κληροδοτήσει στο νησί μία ανεπτυγμένη χριστιανική κοινότητα και εννέα συνολικά επισκοπές. Τα ονόματα των διαδόχων του είναι άγνωστα, διασώθηκαν ωστόσο τα ονόματα των επισκόπων Γορτύνης Φιλίππου και Κνωσού Πινυτού (τέλη 2ουαι.), οι οποίοι υπεράσπισαν την Εκκλησία από τις τότε αιρέσεις, όπως τον μαρκιωνισμό.
Το σημαντικότερο όμως πρόβλημα για την ολοένα και αυξανόμενη χριστιανική κοινότητα του νησιού ήταν ο διωγμός από τους Ρωμαίους αυτοκράτορες. Επί Δεκίου (249-251 μ.Χ.) μαρτύρησαν οι Άγιοι Δέκα Μάρτυρες, επειδή αρνήθηκαν να συμμετάσχουν σε ειδωλολατρικές τελετές. Σύμφωνα με το αγιολόγιο της εκκλησίας μας, αυτοί ήταν: ο Θεόδουλος, ο Σατορνίλος, ο Εύπορος, ο Γελάσιος και ο Ευνικιανός από τη Γόρτυνα, ο Πόμπιος από τη Λεβήνα, ο Αγαθόπους από το Πάνορμο Μυλοποτάμου, ο Βασιλείδης από την Κυδωνία, ο Ζωτικός από την Κνωσό και ο Ευάρεστος από το Ηράκλειο. Επί Διοκλητιανού μαρτύρησε το 304 μ.Χ. ο επίσκοπος Γορτύνης Κύριλλος, την ίδια περίοδο υπολογίζεται ότι θανατώθηκε ο Πέτρος ο Νέος, τον οποίο οι πηγές αναφέρουν ως επίσκοπο Κρήτης, ενώ άγνωστος είναι συνολικά ο αριθμός των επισκόπων, των ιερέων και των λαϊκών που βρήκαν μαρτυρικό θάνατο κατά την αυτή περίοδο των διωγμών.
Λίγα χρόνια αργότερα, με την άνοδο Κωνσταντίνου στο βυζαντινό θρόνο, οι διωγμοί θα σταματούσαν και η χριστιανική Εκκλησία θα λάμβανε επίσημη αναγνώριση από το κράτος. Το Φεβρουάριο του 313 μ.Χ υπογράφτηκε το Διάταγμα των Μεδιολάνων, που αποκαθιστούσε τη θρησκευτική ειρήνη στη Ρωμαϊκή Αυτοκρατορία, και το 325 μ.Χ. συγκλήθηκε η πρώτη Οικουμενική Σύνοδος της Νίκαιας. Αν και δεν διασώζονται πλήρεις επισκοπικοί κατάλογοι, μεταξύ των 318 θεοφόρων Πατέρων που έλαβαν μέρος αναφέρεται και ο Κρήτης Αρτάκιος. Η Σύνοδος ενέταξε την Εκκλησία στις επίσημες δομές της Ρωμαϊκής Αυτοκρατορίας και εισήγαγε το μητροπολιτικό διοικητικό σύστημα. Σύμφωνα με αυτό, η Εκκλησία της Κρήτης οργανώθηκε σε ιδιαίτερη Μητρόπολη, με έδρα την Γόρτυνα, στην οποία υπήχθησαν όλες οι επισκοπές του νησιού. Ο μητροπολίτης έφερε τον τίτλο του αρχιεπισκόπου και η Κρήτη γινόταν μία από τις δώδεκα αρχιεπισκοπές του Ιλλυρικού, όπως χαρακτηριστικά ονομαζόταν τότε η βαλκανική χερσόνησος, υπό τη δικαιοδοσία του πάπα Ρώμης.