Ο θεμέλιος λίθος του Ιερού Ναού τέθηκε στις 25 Μαρτίου του 1862 από τον αρχιερέα Διονύσιο Χαριτωνιάδη μετέπειτα Οικουμενικό Πατριάρχη.

Τα σχέδια του ναού έγιναν από τον Ηπειρώτη αρχιτέκτονα Αθανάσιο Μούση.

Η έκρηξη της Κρητικής επανάστασης το 1866 οδήγησε στην άμεση διακοπή των εργασιών, που συνεχίστηκαν το 1883 και ολοκληρώθηκαν το 1895. Για το κτίσιμο του Ναού πολλοί Ηρακλειώτες προσέφεραν χρηματικά ποσά, ενώ όσοι αδυνατούσαν, προσέφεραν προσωπική εργασία. Η δαπάνη ανέγερσης ανήλθε στις 30 χιλιάδες λίρες χωρίς την προσωπική εργασία των Χριστιανών.

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

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