Κατά την περίοδο της Τουρκοκρατίας, ο Άγιος Μηνάς καθιερώθηκε ως πολιούχος της πόλης του Ηρακλείου και η μνήμη του γιορτάζεται στις 11 Νοεμβρίου. Για να δείξουν την ευγνωμοσύνη τους οι κάτοικοι έχτισαν ως σύμβολο τον καθεδρικό ναό του Αγίου Μηνά, ο οποίος και θεμελιώθηκε το 1862.

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

Τα εγκαίνια του ναού, τελέστηκαν τον Απρίλιο του 1895 από τον Τιμόθεο Ά, Μητροπολίτη Κρήτης, με ιδιαίτερη μεγαλοπρέπεια και στολισμούς.

Ακριβώς δίπλα στον επιβλητικό ναό, στην πλακόστρωτη πλατεία υπάρχει ο μικρός ναός του Αγίου Μηνά, κτίσμα που κατασκευάστηκε πολύ πριν τον πρώτο το έτος 1735, ώστε να στεγαστεί η Μητρόπολη και ο ναός της Αγίας Αικατερίνης.