Ο σημερινός καθεδρικός ναός των Εισοδίων χτίστηκε στη θέση παλαιότερου ναού της Θεοτόκου, ο οποίος ανάγεται στον 14ο αιώνα. Όταν τα Χανιά κατελήφθησαν από τους τούρκους το 1645, ο ναός μετατράπηκε σε σαπωνοποιείο, χωρίς όμως να αλλάξει η διαρρύθμισή του. Μέχρι το 1868 ο ναός, ως σαπωνοποιείο, φέρεται να ανήκει στο γνωστό Τούρκο αξιωματούχο Μουσταφά Πασά Γκιριτλή (Κρητικό). Στο χώρο της ελαιοαποθήκης φυλασσόταν εικόνα της Παναγίας με ακοίμητο καντήλι, σύμφωνα με διαταγή του Μουσταφά. Η παράδοση αναφέρει ότι η επιχείρηση του σαπωνοποιείου ναυάγησε και εγκαταλείφθηκε, ενώ την εικόνα της Θεοτόκου είχε πάρει μαζί του ο τελευταίος τεχνίτης. Όταν ο Μουσταφά έγινε πρωθυπουργός, επί σουλτάνου Μετζίτ, η Χριστιανική Κοινότητα ζήτησε το χώρο για την ανέγερση και πάλι ναού. Ο Μουσταφά, επηρεασμένος από διάφορα προσωπικά γεγονότα, παραχώρησε το χώρο. Ο σουλτάνος έστειλε 100.000 γρόσια και ο γιος του Μουσταφά, Βελή πασάς (διοικητής της Κρήτης τότε) 30.000 γρόσια. Με την ενίσχυση της Χριστιανικής Κοινότητας και παρά τα προβλήματα που προκαλούσε άλλος Οθωμανός, η εκκλησία ανεγέρθηκε τελικά. Η κατασκευή του ναού ολοκληρώθηκε το 1860 στη μορφή της τρίκλιτης βασιλικής με υπερυψωμένο το καλυμμένο από οξυκόρυφη κάμαρα μεσαίο κλίτος. Τα πλάγια κλίτη καλύπτονται από σταυροθόλια και διαιρούνται καθ’ ύψος από το γυναικωνίτη. Στη Βορειοδυτική γωνία του ναού είναι κτισμένο το ψηλό κωδωνοστάσιο. Τα αρχιτεκτονικά στοιχεία του ναού συνδέονται περισσότερο με την παράδοση που διαμορφώθηκε στα χρόνια της Βενετοκρατίας με τους λαξευτούς πεσσούς, τα γείσα και τα πλαίσια των ανοιγμάτων. Ο ανατολικός τοίχος του ναού κοσμείται με μεγάλες και εντυπωσιακές αγιογραφίες έργα των Γ. Καλλιτεράκη, Γ. Σταυράκη, Ε. Τριπολιτάκη και Δ. Κοκότση. Ο ναός, άρρηκτα συνδεδεμένος με τα ιστορικά γεγονότα, υπήρξε άσυλο και καταφύγιο των κατά καιρούς διωκομένων κατά τις εθνικές εξεγέρσεις. Υπέστη σοβαρές ζημιές κατά τους βομβαρδισμούς της πόλης από τους γερμανούς, τον Μάϊο του 1941.