Ο νεότερος ναός του Αγίου Ματθαίου κτίστηκε, πιθανόν ως οικογενειακό παρεκκλήσι, στην αρχή του 17ου αιώνα, στη θέση παλιότερου βυζαντινού ναού, που καταστράφηκε από σεισμό. Μετά την οθωμανική κατάκτηση, παραχωρήθηκε ως μετόχι στο ορθόδοξο μοναστήρι της Αγίας Αικατερίνης στο Όρος Σινά, αντί της Αγίας Αικατερίνης, που μετατράπηκε σε τζαμί. Στους επόμενους αιώνες, μαζί με το ναό του Αγίου Μηνά, αποτελούσαν τις δύο κύριες ορθόδοξες εκκλησίες της πόλης και για αυτό στον περίβολο του κτιρίου, είχαν ταφεί σημαίνοντα πρόσωπα της χριστιανικής κοινότητας.

Ο Άγιος Τίτος υπήρξε ο μεγαλύτερος και επιβλητικότερος ναός της πόλης στα χρόνια της Β’ Βυζαντινής περιόδου και αποτελούσε τη Μητρόπολη της Επισκοπής Κρήτης. Κατά την ενετοκρατία εγκαταστάθηκε εδώ ο Λατίνος αρχιεπίσκοπος, ενώ κατά τη διάρκεια της οθωμανικής περιόδου μετατράπηκε σε τζαμί, με το κωδωνοστάσιο να μετατρέπεται σε μιναρέ. Ο ναός, στην αρχική μορφή του όπως εγκαινιάστηκε το 1446, ήταν μια τρίκλιτη ξυλόστεγη βασιλική.

Ο Ναός χτίστηκε στα πρώτα χρόνια της βενετοκρατίας, δίπλα στο θαλάσσιο τείχος της πόλης και αποτελούσε το Καθολικό της Μονής του τάγματος των Δομινικανών μοναχών. Στην αρχική του μορφή ήταν μονόκλιτος και ξυλόστεγος και σταδιακά προστέθηκαν σε αυτόν τέσσερα παρεκκλήσια. Η αρχιτεκτονική του παρουσιάζει ιδιαίτερο ενδιαφέρον καθώς ενσωματώνει διάφορα χαρακτηριστικά που προδίδουν τη συγγένεια του με κτίσματα του 13ου αιώνα στην Γαλλία και την Ιταλία. Κατά την τουρκοκρατία, μετατράπηκε σε τζαμί. Διαδοχικοί σεισμοί από τον 14ο ως τον 18ο αιώνα προκάλεσαν στον ναό μεγάλες καταστροφές

Είναι ένα από τα πιο παλιά μοναστήρια της Κρήτης, νότια του χωριού Βενεράτο και χτίστηκε πάνω στα ερείπια αρχαίου ναού, όπως βεβαιώνουν τα κιονόκρανα που βρίσκονται στον περίβολο της μονής. Είναι αφιερωμένο στην Κοίμηση της Θεοτόκου και λειτουργεί από τους πρώτους αιώνες της Βυζαντινής Αυτοκρατορίας, ενώ ήκμαζε επί βενετσιάνικης περιόδου. Επί Τουρκοκρατίας έπεσε θύμα της πρωτοφανούς αγριότητας των Τούρκων, πυρπολήθηκε και από τις 70 μοναχές σώθηκαν μόνο τρεις. Ανακαινίστηκε στα τέλη του 19ου αιώνα και ακολούθησε μια νέα περίοδος ακμής. Ένα από τα πιο σημαντικά στοιχεία της Παλιανής είναι η Αγία Μυρτιά, μια αιωνόβια μυρτιά που βρίσκεται στα νότια του Καθολικού και η οποία εορτάζεται στις 23 Σεπτεμβρίου, καθώς κατά την παράδοση στον κορμό της είχε βρεθεί η εικόνα της Παναγίας.