ΤΟ ΒΥΖΑΝΤΙΟ προσπάθησε πολλές φορές να ανακτήσει την Κρήτη. Τελικά, το πέτυχε τον Μάρτιο του 961 ο Νικηφόρος Φωκάς, ο μετέπειτα αυτοκράτορας (963-969). Η ανάκτηση της νήσου αποτέλεσε την αφετηρία της Β' Βυζαντινής περιόδου (961-1204). Αντιμετωπίστηκε αμέσως το πρόβλημα της επαναφοράς του ποιμνίου στους κόλπους της Εκκλησίας, καθώς και ο εκχριστιανισμός των Αράβων που παρέμειναν στην Κρήτη μετά την απελευθέρωση της.
Ο Νικηφόρος Φωκάς, βαθιά θρησκευόμενος ο ίδιος, είχε από νωρίς αναγνωρίσει αυτό το πρόβλημα. Προσκάλεσε, ενώ ακόμη πολιορκούσε τον Χάνδακα, τον άγιο Αθανάσιο τον Αθωνίτη, ο οποίος τον επισκέφθηκε στο Βυζαντινό στρατόπεδο. Στη συνέχεια έστειλε μηνύματα σε διάφορα μοναστικά κέντρα, προσκαλώντας κληρικούς για να διδάξουν την ορθή πίστη, όπως ήταν ο Νίκων ο Μετανοείτε και ο Ιωάννης ο Ξένος.
Όλοι σχεδόν οι υπόλοιποι κληρικοί και ιεράρχες που έζησαν σ' αυτήν την περίοδο μας είναι γνωστοί απλώς ως ονόματα. Όμως υπάρχουν ενδείξεις ότι ο θρησκευτικός, πνευματικός και καλλιτεχνικός Βίος παρουσίασε αξιόλογη ανάπτυξη, που ήλθε σταδιακά και με την πάροδο του χρόνου. Τον 12ο αιώνα, ταυτόχρονα με την οικονομική ανάπτυξη, η Κρήτη διέθετε αναπτυγμένη θρησκευτική, πνευματική και καλλιτεχνική ζωή. Ο κρητικός λαός διαφύλαξε τη θρησκευτική αυτοσυνειδησία του.Στην εσωτερική οργάνωση της Εκκλησίας παρατηρείται η αλλαγή της έδρας και του ονόματος πολλών Επισκοπών και η σταθερή πλέον ύπαρξη δέκα Επισκοπών υποκείμενων στη Μητρόπολη Κρήτης. Η διαδικασία των αλλαγών αυτών πρέπει να ξεκίνησε κατά την περίοδο της Αραβοκρατίας και να οριστικοποιήθηκε μετά το 961. Έδρα της Μητρόπολης ήταν αρχικά και πάλι η Γόρτυνα, αλλά σύντομα μετακινήθηκε στον Χάνδακα (σημερινό Ηράκλειο), όπου παραμένει από τότε. Η αλλαγή της έδρας μιας Επισκοπής είχε ως αιτία την παρακμή του οικισμού, στον οποίο μέχρι τότε έδρευε, οπότε η μετακίνηση συνοδευόταν συχνά και από αλλαγή του ονόματος. Κατά την περίοδο αυτή δεν υπάρχουν πια οι Επισκοπές Ηρακλείου, Φοίνικος και Κανδάνου.
Η Επισκοπή Κνωσού διατήρησε το όνομα της, αλλά η έδρα της ήταν μάλλον ο «Βούργος» (προάστια) του Χάνδακα. Οι Επισκοπές Κισάμου, Χερσονήσου, Σητείας, Ιεράπετρας και Αρκαδίας διατήρησαν το όνομα τους, αλλά οι έδρες τους μεταφέρθηκαν σε χωριά που πήραν αργότερα το όνομα Επισκοπή. Αντίθετα, η Κυδωνίας άλλαξε το όνομα της σε Αγιάς με έδρα το ομώνυμο χωριό. Στην τωρινή περιφέρεια της Μητροπόλεως Ρεθύμνης και Αυλοποτάμου, η Επισκοπή Λάμπης (Λάππας) άλλαξε το όνομα της σε Καλαμώνος, αφού μετακινήθηκε στο ομώνυμο χωριό Καλαμών(;), που ονομάστηκε Μεγάλη Επισκοπή και σήμερα Επισκοπή, η Συβρίτου σε Αγρίου, στην τοποθεσία που είναι γνωστή ως Βιράν Επισκοπή και η Ελευθέρνης σε Αυλοποτάμου (ή Μυλοποτάμου), με έδρα το ομώνυμο χωριό που σήμερα είναι γνωστό ως Επισκοπή.
Γενικά, η επιστροφή της Κρήτης στο Βυζάντιο έφερε έναν καινούργιο άνεμο ακμής και πολιτιστικής ανάτασης, παρά τον βραδύ ρυθμό της ενσωμάτωσής της στην ιεραρχία των Εκκλησιών του Πατριαρχείου. Η χαρακτηριστική επιτυχία όλων των προσπαθειών δεν ήταν άσχετη με τη θέση της νήσου μεταξύ Ανατολής και Δύσης, η οποία ευνόησε την οικονομική ανάπτυξη και την κοινωνική πρόοδο του λαού της και διευκόλυνε την εκκλησιαστική της αναδιοργάνωση. Οι αλλαγές έγιναν αισθητές σε όλους τους τομείς, στη θρησκευτική ζωή, στην οικοδόμηση ναών, στην τέχνη, στα μοναστηριακά ιδρύματα, όπως η μονή Μυριοκεφάλων, η Αγία Αικατερίνη του Σινά και το μοναστηριακό συγκρότημα στα Λατζιανά. Από τον 12ο αιώνα, η Κρήτη έχει θαυμάσιους τοιχογραφημένους ναούς. Κρητικοί καλλιτέχνες φαίνεται πως μπόρεσαν πολύ γρήγορα να ακολουθήσουν τις καλλιτεχνικές τάσεις του Βυζαντίου.
Ο διασημότερος από τους κληρικούς που ήλθαν και έδρασαν στην Κρήτη ήταν ο όσιος Νίκων ο Μετανοείτε, που έμεινε στο νησί και δίδαξε επτά ολόκληρα χρόνια. Γεννήθηκε στον Πόντο μεταξύ 920 και 925 και πέθανε στη Σπάρτη περ. το 998. Ήταν μοναχός και ιεραπόστολος, αναμορφωτής του μοναχικού βίου κυρίως στην Κρήτη και την Πελοπόννησο, και εξέχουσα πνευματική μορφή στον Ελλαδικό χώρο κατά το β' μισό του 10ου αιώνα.Για το πολύπλευρο ιεραποστολικό έργο του, η Ορθόδοξη Εκκλησία τον ανακήρυξε όσιο (26 Νοεμβρίου).
Η δεύτερη μεγάλη προσωπικότητα του μοναστικού βίου, που έδρασε στο τέλος του 10ου και στις αρχές του 11ου αιώνα στην Κρήτη, ήταν ο Ιωάννης ο Ξένος, από το χωριό Σίβα Πυργιώτισσας Ηρακλείου. Κινήθηκε στις περιοχές Ρεθύμνου και Χανίων, σε αντίθεση με τον Νίκωνα, που έδρασε περισσότερο στην κεντρική και ανατολική Κρήτη. Το έργο του δεν αφορούσε στην ιεραποστολή, αλλά στην ίδρυση μοναστηριών και ναών. Ο Ξένος ίδρυσε το σπουδαίο μοναστήρι των Μυριοκεφάλων στην επαρχία Ρεθύμνου, καθώς και διάφορα μετόχια της μονής, την οποία προίκισε με σημαντικά περιουσιακά στοιχεία. Για τη σπουδαία προσφορά του, η Ορθόδοξη Εκκλησία τον ανακήρυξε όσιο (20 Σεπτεμβρίου).
