Όπως αναφέρεται στις πράξεις των αποστόλων, κεφ. 27, στίχος 8, ο Παύλος, οδηγούμενος δέσμιος ως αιχμάλωτος στη Ρώμη για να δικασθεί τον Οκτώβριο του 59 μ.Χ., κατέληξε στα νότια της Κρήτης, στους Καλούς Λιμένες ως ναυαγός «εἰς τόπον τινά καλούμενον Καλούς Λιμένας, ᾧ ἐγγύς ἦν πόλις Λασαία» (Πράξ. 27, 8).

Ενώ το 62 μ.Χ. μετά την αποφυλάκισή του, κατά την δεύτερη αποστολική περιοδεία του,  πήγε στις περιοχές των Καλών Λιμένων και στη Γόρτυνα της Μεσσαράς. Η παραμονή του Παύλου στην Κρήτη ήταν σύντομη και το δυσχερές έργο της οργάνωσης της πρώτης κρητικής Εκκλησίας το ανέθεσε στον συνεργό και συνοδοιπόρο του Τίτο, στον οποίο γράφει "Τούτου χάριν κατέλιπόν σε εν Κρήτη, ίνα τα λείποντα επιδιορθώση, και καταστήσης κατά πόλιν πρεσβυτέρους, ως εγώ σοι διεταξάμην " (Τίτ. α΄, 5).