Σε μικρή απόσταση, δυτικά από τον ναό της Αγίας Αικατερίνης υπάρχει ένας μικρός ταπεινός ναός, που ήταν αφιερωμένος στον Άγιο Μηνά, ο οποίος από το 1735 είχε καθιερωθεί ως πολιούχος της πόλης, με εξαιρετικής τέχνης τέμπλο και εικόνες του ζωγράφου Γ. Καστροφύλακα.
Το 1862 και μετά από περιόδους επαναστάσεων ενάντια στους Τούρκους, οι Χριστιανοί του Ηρακλείου αποφάσισαν να κατασκευάσουν ένα λαμπρότερο ναό για τον πολιούχο Άγιο τους, σε σχέδια του πρακτικού αρχιτέκτονα Αθανάσιου Μούση, ο οποίος ήλθε για αυτό το λόγο από την Κωνσταντινούπολη. Οι εργασίες της ανέγερσης του ναού διακόπηκαν κατά την διάρκεια της επανάστασης του 1866-1869 και τελικά ολοκληρώθηκε το 1895.
Ο Άγιος Μηνάς είναι ένας από τους επιβλητικότερους ναούς της Κρήτης με εξαίρετο εσωτερικό διάκοσμο και εξωτερική μεγαλοπρέπεια.
