Με την ανάκτηση της Κρήτης από το Νικηφόρο Φωκά, η έδρα της επισκοπής μεταφέρεται από τη Γόρτυνα στον Χάνδακα που γίνεται τώρα η πρωτεύουσα του νησιού. Ο νέος μητροπολιτικός ναός που είναι ο επισημότερος και μεγαλύτερος στην πόλη είναι αφιερωμένος στον Απόστολο Τίτο. Εδώ, μεταξύ των άλλων κειμηλίων, συγκεντρώθηκαν η Τιμία Κάρα του Αποστόλου Τίτου και η θαυματουργή εικόνα της Μεσοπαντίτισσας. Οι Βενετοί, όταν κατάλαβαν την Κρήτη, εγκατάστησαν στην ορθόδοξη επισκοπή τον λατίνο αρχιεπίσκοπο μετατρέποντας το ναό του Άγιου Τίτου σε επισκοπή λατίνων. Στα μέσα του 15ου αι. ο ναός ανακαινίζεται από τον λατίνο αρχιεπίσκοπο Φ.Ντάντολο. Όμως άλλες καταστροφές θα προκληθούν στο ναό από σεισμούς και πυρκαϊά με αποτέλεσμα να ξανακτιστεί εξαρχής γύρω στα 1557. Είχε σχήμα βασιλικής, σχεδόν τετράγωνο, χωρίς κόγχες, με τρούλο στη μέση και κωδωνοστάσιο στη νοτιοδυτική του γωνία. Το εσωτερικό του χωριζόταν σε τρία κλίτη με δύο τοξοστοιχίες. Κατά την περίοδο της τουρκοκρατίας ο ναός παραχωρήθηκε στον Φαζίλ Αχμέτ Κιοπρουλή και μετατράπηκε σε τζαμί, ενώ το κωδωνοστάσιο σε μιναρέ. Ο μεγάλος σεισμός του 1856 καταστρέφει το ναό που κτίζεται πάλι από την αρχή. Μετά την ανταλλαγή των πληθυσμών, η Εκκλησία της Κρήτης επισκεύασε κατάλληλα το ναό και το 1925 αφιερώθηκε και πάλι στον Απόστολο Τίτο. Ανατολικά του ναού ήταν το μέγαρο της Αρχιεπισκοπής.