Οι διωγμοί, που εξαπολύουν διάφοροι ρωμαίοι αυτοκράτορες εναντίον των οπαδών της νέας θρησκείας, πλήττουν και τη χριστιανική κοινότητα της Κρήτης, με πιο γνωστές περιπτώσεις αυτές των Αγίων Δέκα, που μαρτύρησαν στις 23 Δεκεμβρίου του 250 μ.Χ., και του επισκόπου Γορτύνης Κύριλλου, που μαρτύρησε στις 9 Ιουλίου 304 μ.Χ.
Η επικράτηση του Χριστιανισμού στο νησί ολοκληρώνεται κατά τον 4ο αιώνα, οπότε και οργανώνεται συστηματικά η Κρητική Εκκλησία.
Διοικητικά, κατά τους πρώτους αιώνες, η αρχιεπισκοπή της Κρήτης υπάγεται κατά κύριο λόγο στο Πατριαρχείο της Ρώμης. Στα μέσα του 8ου αι., όμως, προσαρτάται οριστικά στο Πατριαρχείο Κωνσταντινούπολης, ως συνέπεια της εξασθένησης της βυζαντινής κυριαρχίας στην Ιταλία και πιθανόν της εικονομαχικής διαμάχης.