Μετά την ανάκτηση της Κρήτης από τον Νικηφόρο Φωκά το 961 μ.Χ. αρχίζει η λεγόμενη δεύτερη βυζαντινή ή μεσοβυζαντινή περίοδος στην Κρήτη (961-1204 μ.Χ.). Μέσα από ένα καλά οργανωμένο σχέδιο οικιστικής, οχυρωματικής και εκκλησιαστικής ανασυγκρότησης του νησιού κατά την περίοδο αυτή, η Κρήτη θα ανακτήσει την αίγλη του παρελθόντος και θα επιδείξει μια αξιοσημείωτη ανάπτυξη σε όλα τα επίπεδα. Κοντά στο Χάνδακα, που θα αποτελέσει την πολιτική αλλά και θρησκευτική έδρα της Εκκλησίας της Κρήτης, θα ανοικοδομηθεί ένα μεγάλο φρούριο, ενώ μια σειρά από φρούρια θα κτιστούν επίσης σε αρκετές περιοχές της ενδοχώρας. Το νησί θα εποικιστεί με ξένους στρατιώτες και θα δοθεί βάρος στην ανασυγκρότηση της οικονομικής βάσης της υπαίθρου.
Έχοντας ήδη προνοήσει για την εξασφάλιση της αμυντικής ικανότητας του νησιού και την αναγέννηση της υπαίθρου, ο Νικηφόρος Φωκάς θα επιδοθεί με ιδιαίτερο ζήλο στην επαναφορά του ποιμνίου στους κόλπους της Εκκλησίας. Οι Άραβες φαίνεται ότι ήταν ανεκτικοί απέναντι στο χριστιανικό δόγμα, ωστόσο είχαν απομακρύνει την εκκλησιαστική ιεραρχία, η οποία έχασε τα ερείσματά της στον ντόπιο πληθυσμό. Ο Φωκάς γνώριζε το πρόβλημα και ήδη, ενώ ακόμη πολιορκούσε τον Χάνδακα, είχε προσκαλέσει τον άγιο Αθανάσιο τον Αθωνίτη, ο οποίος τον επισκέφθηκε στο βυζαντινό στρατόπεδο. Μετά τη λήξη των εχθροπραξιών, θα ξεκινήσει ένας δεύτερος γύρος επισκέψεων σημαντικών ιεραρχών και λογίων της εποχής, μεταξύ των οποίων ήταν και ο Άγιος Νίκων ο Μετανοείτε, που θα περιοδεύσει στην ανατολική κυρίως Κρήτη επί πέντε συναπτά έτη.
Στην εσωτερική τώρα οργάνωση της Εκκλησίας παρατηρούνται σημαντικές αλλαγές. Η Εκκλησία της Κρήτης αναφέρεται ως μητρόπολη στην εκκλησιαστική τάξη του Οικουμενικού Θρόνου και ο προκαθήμενος της έχει ως έδρα αρχικά τη Γόρτυνα και έπειτα το Χάνδακα. Η θέση της Εκκλησίας της Κρήτης στην ιεραρχία των «τακτικών» δεν ήταν σταθερή, ούτε όμως και ο αριθμός των επισκοπών της, που κυμαίνονταν από δέκα ως δώδεκα (όπως π.χ. φαίνεται στο «τακτικό» του Βασιλείου του Βουλγαροκτόνου το 980 μ.Χ.). Μαζί με την αλλαγή της μητροπολιτικής έδρας, φαίνεται ότι άλλαξε η έδρα, καθώς και η ονομασία των παραπάνω επισκοπών. Έτσι, βλέπουμε ότι η επισκοπή Κυδωνίας μετονομάστηκε σε Αγιάς, με τη μεταφορά της στο ομώνυμο οικισμό, η επισκοπή Λάππας μετονομάστηκε σε Καλαμώνος και μεταφέρθηκε στη Μεγάλη Επισκοπή Ρεθύμνου (σήμερα Επισκοπή), η επισκοπή Αυλοποτάμου μετονομάστηκε σε Μυλοποτάμου, από τον ομώνυμο οικισμό στον οποίο μεταφέρθηκε, και η επισκοπή Ελευθέρνης μετονομάστηκε σε Αρίου, ενώ είχε ήδη μεταφερθεί στη Βιράν Επισκοπή. Η Επισκοπή Κνωσού διατήρησε το όνομα της, ενώ οι επισκοπές Κισάμου, Χερρονήσου, Σητείας, Ιεράπετρας και Αρκαδίας διατήρησαν το όνομα τους, ωστόσο οι έδρες τους μεταφέρθηκαν σε οικισμούς που μετονομάστηκαν σε Επισκοπή.
Αλλαγές παρατηρήθηκαν και στην ανοικοδόμηση των ναών. Βασιλικές, σταυροειδείς με τρούλο, μικροί και μεγάλοι ναοί και μοναστήρια κτίζονταν σε όλο το μήκος και πλάτος του νησιού. Η ερειπωμένη σήμερα Μονή της Αγίας Βαρβάρας στα Λατζιανά Κισάμου, η Μονή Παλιανής στο Βενεράτο Ηρακλείου, ο ναός της Παναγίας της Ζερβιώτισσας στο Στύλο Αποκορώνου αποτελούν δείγματα μιας λαμπρής αρχιτεκτονικής αναγέννησης, μιας μνημειακής τέχνης ιδιαίτερα υψηλού επιπέδου, η οποία συνοδεύτηκε με την ανάπτυξη μιας πολύ αξιόλογης καλλιτεχνικής τάσης στην αγιογραφία. Οι Κρητικοί καλλιτέχνες φαίνεται ότι μπορούσαν να ακολουθήσουν άνετα τις ακαδημαϊκές, ή και της Κομνήνειας τέχνης, τάσεις των βυζαντινών αγιογράφων, όπως μπορεί να διακρίνει κανείς σε σωζόμενους τοιχογραφικούς διακόσμους ναών, όπως της Παναγίας στο Φόδελε και του Μιχαήλ Αρχαγγέλου (Ροτόντα) στην Επισκοπή Κισάμου αντιστοίχως.
Την ίδια περίοδο ιδρύονταν μετόχια μονών που βρίσκονταν εκτός Κρήτης, όπως το μετόχι της Αγίας Αικατερίνης του Σινά στο Χάνδακα και το μετόχι του Αγίου Ιωάννου του Θεολόγου στην Πάτμο, το οποίο μάλιστα προικοδοτήθηκε με τεράστια περιουσία από την αυτοκρατορική αυλή. Μια μεγάλη προσωπικότητα του μοναστικού χώρου που θεμελίωσε αρκετούς ναούς και μοναστήρια ήταν ο λόγιος και πολυγραφότατος άγιος της Εκκλησίας Ιωάννης ο Ξένος από τον οικισμό Σίβας Αστερουσίων. Έδρασε στο τέλος του 10ου και στις αρχές του 11ου αι., ιδιαίτερα στις περιοχές Ρεθύμνου και Χανίων, κτίζοντας μοναστηριακούς και μη ναούς, όπως της Αντιφωνήτριας στα Μυριοκέφαλα, του Αγίου Γεωργίου στο Μέλικα, του Αγίου Γεωργίου στην Πηγή, του Αγίου Παταπίου στον ποταμό Μουσέλα κοντά στην Αργυρούπολη, της Ζωοδόχου Πηγής στον Αλικιανό, του Αγίου Παύλου στην ομώνυμη παραλία των Σφακίων, και του Αγίου Γεωργίου στον Αζωγυρέ Σελίνου.
Ιδιωτικούς ναούς έκτιζαν και οι πλούσιοι κάτοικοι του νησιού, όπως τα μέλη των 12 ευγενών οικογενειών που στάλθηκαν από την Κωνσταντινούπολη κατά τα τέλη της δεύτερης βυζαντινής περιόδου, των λεγόμενων Αρχοντόπουλων. Μέχρι και σήμερα σώζονται ναοί με οικόσημα ή επιγραφές αυτών των οικογενειών, όπως ο Προφήτης Ηλίας στα Περβόλια Χανίων, που ανήκε στην οικογένεια των Καλλέργηδων, ή ο ναός της Παναγίας της Σκορδυλιανής στους Αρμένους Αποκορώνου, που σε ανακαινισμένη εκ βάθρων σήμερα μορφή, βρίσκεται στο ομώνυμο μετόχι της οικογένειας των Σκορδύληδων.
Από τους μητροπολίτες της περιόδου αυτής διασώθηκαν τα ονόματα του Ηλία, του Ιωάννη (1166-1172 μ.Χ.) και του Νικολάου, ο οποίος το 1211 μ.Χ. κατέφυγε στη Νίκαια της Βιθυνίας, όταν η Κρήτη καταλήφθηκε από τους Ενετούς. Μαζί με αυτόν έφυγαν οι επίσκοποι Πέτρας Γρηγόριος και Αρκαδίας Ιωάννης.