Μετά την περίοδο της Αραβοκρατίας και την ανάκτηση της Κρήτης το 961 από τους Βυζαντινούς, αποκαταστάθηκε και η εκκλησία της Κρήτης. Ο ερειπωμένος Χάνδακας χτίστηκε ξανά εκ θεμελίων και έγινε πρωτεύουσα του νησιού. Την περίοδο αυτή πρέπει να κτίστηκε ο ναός που αφιερώθηκε στον Ισαπόστολο Τίτο, για να συνεχιστεί η παλαιά θρησκευτική παράδοση, που είχε διακοπεί από τους Άραβες που κατέστρεψαν τη Γόρτυνα, την πρώτη θρησκευτική πρωτεύουσα του νησιού στην οποία υπήρχε ο ναός του Αγίου Τίτου, τμήματα του οποίου σώζονται και σήμερα.

Στο νέο ναό απόθεσαν την κάρα του Αγίου Τίτου, τη θαυματουργή εικόνα της Παναγίας της Μεσοπαντίτισσας και άλλα λείψανα και κειμήλια που είχαν σώσει Χριστιανοί από το ναό της Γόρτυνας. Στον περίβολο του ναού έθαβαν τους Αρχιεπισκόπους, τους Κατεπάνω και τους Στρατηγούς της Βυζαντινής περιόδου. Η πρακτική αυτή συνεχίστηκε και τις επόμενες περιόδους.