Ο ναός, που εγκαινιάστηκε από τον Φαντίνο Ντάντολο το 1446, ήταν μια τρίκλιτη ξυλόστεγη βασιλική με περίτεχνη διακόσμηση. Στη δυτική του πρόσοψη είχε τρεις πόρτες, όπως φαίνεται σε σχέδιο του ζωγράφου Μανέα Κλώντζα.

Ο ναός καταστράφηκε κατά το σεισμό του 1856 και ανοικοδομήθηκε το 1869, σε σχέδια του Ηπειρώτη αρχιτέκτονα Αθανάσιου Μούση. Κτίζεται νέο μεγαλοπρεπές τέμενος εκλεκτικιστικού ρυθμού. «Το χαρίεν αυτό αρχιτεκτονικόν καλλιτέχνημα, που δεν υπήρξε παρόμοιον του εν Κρήτη», όπως λέει ο Ξανθουδίδης, «με τα πολλά παράθυρά του, με τα καμπυλωτά και τοξωτά περιγράμματά των, παρουσιάζει όψη αραβική, όπως το βλέπομε σήμερα.

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