Η πρώτη μητρόπολη της Κρήτης ήταν στη Γόρτυνα, πρωτεύουσα του θέματος της Κρήτης, την πρώτη βυζαντινή περίοδο 323-828μ.Χ. και ο μητροπολιτικός ναός του αποστόλου Τίτου, από τους πρώτους χριστιανικούς ναούς της νήσου, που κτίστηκε τον ΣΤ' αιώνα, ή πιθανόν, και προηγουμένως, αφού μέσα στο ναό βρέθηκε, νόμισμα του αυτοκράτορα Ιουστίνου 518-527μ.Χ.

Το 961μ.Χ. ο Νικηφόρος Φωκάς ανέκτησε την Κρήτη και ο Χάνδακας έγινε η νέα πρωτεύουσα της νήσου, όπου εγκαταστάθηκαν οι νέες αρχές και, φυσικά, η Κεφαλή της Εκκλησίας της Κρήτης. 'Ηδη το 980 μ.Χ., δηλαδή 19 χρόνια μετά την ανάκτηση της Κρήτης, αναφέρεται στο τακτικό Βασιλείου του Βουλγαροκτόνου: Τω της νήσου Κρήτης -εννοείται - μητροπολίτη, όπου αναφέρονται και οι επίσκοποι 12 επισκοπών της Κρήτης, που ανασυστήθηκαν με τα παλιά ονόματα, Γορτύνης, Κνωσού, Αρκαδίας, Χερρονήσου, Αυλοποτάμου κ.λ.π.

Αφού αναφέρεται το 980 μητροπολίτης Κρήτης βέβαια θα υπήρχε και μητροπολιτικός ναός στη νέα έδρα ο οποίος ήταν Άγιος Τίτος, ως συνέχεια του προηγούμενου ναού στη Γόρτυνα. Ο ναός κτίστηκε όπου είναι και σήμερα, στη θέση που θα ήταν το μουσουλμανικό τέμενος των Αράβων.

Ύστερα από τη διάλυση της βυζαντινής Αυτοκρατορίας το 1204 και την εγκατάσταση των Βενετών στη Κρήτη, ο Καθολικισμός έδιωξε το μητροπολίτη και τους επισκόπους και στη θέση τους εγκατέστησε καθολικούς. Η λατρεία στο μητροπολιτικό ναό συνεχίστηκε από τους καθολικούς χωρίς ν' αλλάξουν τίποτε από το λατρευτικό διάκοσμο του ναού.

Η κατάκτηση της Κρήτης από τους αλλόθρησκους Τούρκους άλλαξε ριζικά την κατάσταση. Το Πατριαρχείο θεωρούσε βέβαιη την επανεγκατάσταση στην Κρήτη των παλαιών εκκλησιαστικών αρχών και έστειλε τον πρώτο χρόνο της τουρκικής κατάκτησης, 1645μ.Χ., μητροπολίτη τον Κρητικό Νεόφυτο Πατελάρο

Ο Κιουπρουλής, αφού έγινε κύριος του Χάνδακα στις 4 Οκτωβρίου 1669, όλες οι εκκλησίες - 135 , που αναφέρονται στο χάρτη του Βερντμύλερ της τελευταίας δεκαετίας της Βενετοκρατίας- μετατράπηκαν σε τζαμιά και λουτρά. Ο ναός του Αγίου Τίτου έγινε του ίδιου του πορθητή βεζίρη Κιουπρουλή, γνωστό έκτοτε, μέχρι το 1922, Βεζίρ Τζαμί

Οι Χριστιανοί ραγιάδες ήταν απαραίτητοι στο νέο κατακτητή. Για να προσελκύσει στην πόλη Χριστιανούς κατοίκους ο Κιοπρουλής λέει στο διερμηνέα και σύμβουλό του Παναγιώτη Νικούσιο Μαμωνά, να βρει μια εκκλησία απόκεντρη και άσημη, για να εγκατασταθεί ο μητροπολίτης Κρήτης Νεόφυτος Πατελάρος, που είχε εκλεγεί από το 1645, και είχε ακολουθήσει τον τουρκικό στρατό στην Κρήτη. Ο Νικούσιος υπέδειξε την εκκλησία του Αγίου Ματθαίου.'Ομως για άγνωστους λόγους, ο Νικούσιος δεν παρέδωσε την εκκλησία στο μητροπολίτη Νεόφυτο Πατελάρο αλλά στους Σιναϊτες μοναχούς.

Έτσι ο μητροπολίτης δεν είχε καμιά εκκλησία για τις θρησκευτικές ανάγκες των Χριστιανών. Το πλέον θλιβερό ήταν ότι οι Σιναϊτες για πολλά χρόνια εμπόδιζαν την οικοδόμηση μητροπολιτικού ναού παρεμβαίνοντας δολίως στις τουρκικές αρχές, ώστε να έχουν την αποκλειστική νομή των προσφορών και των δωρεών των Χριστιανών.

Το θέμα της μητρόπολης Κρήτης απασχόλησε σοβαρά το Πατριαρχείο.

Το πρόβλημα λύνεται το 1725μ.Χ. με την εκλογή ως Μητροπολίτη Κρήτης τον Γεράσιμο Λετίτζη (1725-1755). Ήταν Κρητικός και καταγόταν από το χωριό Βενεράτο Τεμένους. Ο Γεράσιμος γνώριζε καλά την κατάσταση στην Κρήτη. Έθεσε όμως όρο στο Οικουμενικό Πατριαρχείο να του χορηγηθεί σουλτανική άδεια για την ανέγερση μητροπολιτικού ναού του Χάνδακα. Πράγματι η άδεια χορηγήθηκε το 1725. Σύμφωνα με το έγγραφο αυτό, ο Γεράσιμος διέθετε ιδιόκτητη βακουφική κατοικία στον Χάνδακα, στον περίβολο της οποίας υπήρχε παλαιά εγκαταλελειμμένη εκκλησία, την οποία θα ανοικοδομούσε ως οίκο προσευχής. Έτσι με το έγγραφο αυτό κατόρθωσε να υπερνικήσει τα πολλά τοπικά προβλήματα και να χαρίσει στη χριστιανική κοινότητα της τουρκοκρατούμενης πόλης το θρησκευτικό της κέντρο. Τα εγκαίνια της ιστορικής αυτής εκκλησίας έγιναν με μεγαλοπρέπεια στις 10 Νοεμβρίου 1735, ημέρα Δευτέρα.

Ο παλαιός ναός του Αγίου Μηνά .Σχέδιο του Θεοδ.Κόκκινου (1938), στο βιβλίο του Γ.Συλαμιανάκη.

Είναι αμφίβολο, αν χωρίς αυτήν την ευλογημένη παρουσία του Γεράσιμου Λετίτζη, θα αποκτούσε ποτέ το Ηράκλειο μητροπολιτικό ναό κατά τους χαλεπούς εκείνους καιρούς.

Ο μητροπολίτης κέρδισε τη γενική εκτίμηση και θεωρήθηκε δικαίως ως ο μέγας προστάτης και ευεργέτης των Χριστιανών του Χάνδακα.

Ο ναός αυτός που καθιερώθηκε στην Υπαπαντή της Θεοτόκου (βόρειο κλίτος) και στον άγιο Μηνά (νότιο κλίτος) αποτέλεσε η εστία, η ψυχή και το ενωτικό κέντρο των χριστιανών του τουρκοκρατούμενου Χάνδακα, που βρήκαν έπειτα από πολλές δεκαετίες αβεβαιότητας και φόβου, ένα σταθερό στήριγμα θρησκευτικής και εθνικής ζωής. Έτσι ο Άγιος Μηνάς συνδέθηκε με την πόλη του Ηρακλείου, της οποίας είναι έκτοτε ο προστάτης και άγρυπνος φρουρός. Την αγάπη και τον σεβασμό των κατοίκων προς τον άγιο τους αποδεικνύει όλη η ζωή και η νεότερη ιστορία του Ηρακλείου.