Ο Απόστολος Παύλος κατά την δεύτερη αποστολική του περιοδεία μετά την απελευθέρωσή του από την Ρώμη ( 62-63 μ.χ) κήρυξε τον χριστιανισμό στην Κρήτη, την συνέχιση του έργου του ανέθεσε στο πιστό μαθητή του Τίτο.Η λατρεία του Αγίου Τίτου υπήρξε πάντα ζωηρή στην Κρήτη.

Λίγα στοιχεία σώζονται για τους πρώιμους χριστιανικούς χρόνους, όμως αξίζει να αναφέρουμε ότι οι πρώτοι μάρτυρες χριστιανοί ήταν οι «Οι Άγιοι Δέκα» επί αυτοκράτορα Δεκίου 23 Δεκεμβρίου το 250 μ.χ.

Αργότερα θα μαρτυρήσει και ο επίσκοπος Γορτύνης Κύριλλος ( 9 Ιουλίου 304) ενώ είναι άγνωστο πότε μαρτύρησε ο Άγιος Θεόφιλος (31 Μαρτίου).