O ναός του Αγίου Τίτου κατασκευάστηκε αρχικά μετά την απελευθέρωση της Κρήτης από το Νικηφόρο Φωκά το 961 μ.Χ. Την βενετσιάνικη περίοδο παρότι μετατράπηκε σε καθολικό ναό, δεν έχασε την βυζαντινή φυσιογνωμία γιατί διατηρήθηκαν τόσο ο διάκοσμος όσο και τα ορθόδοξα κειμήλια και οι βυζαντινές εικόνες. Σημαντικές ζημιές φαίνεται να υφίσταται το 1446 από σεισμό οι οποίες αποκαθίστανται αμέσως. Το 1557 σχεδόν ξανακτίστηκε από τα θεμέλια μετά από την μεγάλη πυρκαγιά του 1554. Κατά την ανοικοδόμηση του 1557 αποκτά τετράγωνο σχήμα Βασιλικής με τρούλο στο κέντρο και κωδωνοστάσιο στην νοτιοδυτική γωνία. Επί Τουρκοκρατίας μετατράπηκε σε τζαμί.

Αυτός ο ναός καταστράφηκε ολοσχερώς από το μεγάλο σεισμό του 1856 και ξανακτίστηκε εκ θεμελίων σε σχέδια του πρακτικού αρχιτέκτονα Μούση ο οποίος είχε σχεδιάσει και τον Άγιο Μηνά. Ο ναός συνέχισε να λειτουργεί σαν τζαμί έως και την περίοδο του 1922 περίπου. Το 1925 μετά από επισκευές και μετατροπές που υπέστη λειτούργησε ξανά σαν ορθόδοξη εκκλησία, 700 χρόνια περίπου μετά την κατάληψη της Κρήτης από τους Βενετσιάνους και τους Τούρκους στην συνέχεια.  Σήμερα ο Άγιος Τίτος με την ομώνυμη πλατεία του είναι ένα από τα ομορφότερα σημεία της πόλης του Ηρακλείου, με τον μεγάλο πλάτανο να δεσπόζει ανάμεσα στα κτίρια της Λότζιας και του ναού.!