Δεν υπάρχουν αρκετές πληροφορίες για τη λατρεία του αγίου Μηνά στην Κρήτη κατά την βυζαντινή περίοδο της κρητικής ιστορίας (330-1204μ.Χ.). Είναι πολύ πιθανό να πέρασε η λατρεία του στην Κρήτη από την Αίγυπτο μέσω των εμπορικών δρόμων Εξ' άλλου ανέκαθεν η Εκκλησία της Κρήτης είχε στενές σχέσεις με την Αίγυπτο.

Συναξαριακές μαρτυρίες μας πληροφορούν ότι δυο τουλάχιστον από τους μεγάλους ιεράρχες επισκόπους Γορτύνης και άγιους της Κρήτης, ο Κύριλλος, μάρτυρας κατά τον μεγάλο διωγμό του Διοκλητιανού και Μαξιμιανού , και ο Ευμένιος (7ος αι.) είχαν σχέσεις με την Αίγυπτο. Είναι πιθανόν ότι επί του Γορτύνης Ευμενίου ή επί των διαδόχων του, τον 7ο ή 8ο αιώνα, ο επιφανέστερος των αγίων της Αιγύπτου Μηνάς ο μεγαλομάρτυρας και θαυματουργός θα έγινε γνωστός και στην Εκκλησία της Κρήτης.

Σήμερα γνωρίζουμε ότι υπήρχε ναός του Αγίου Μηνά στην περιοχή του Ηρακλείου κατά τη δεύτερη βυζαντινή περίοδο της Κρήτης (961-1204μ.Χ.). Η αρχαιότερη μαρτυρία για την ύπαρξη της εκκλησίας αυτής χρονολογείται το 1320 και βρίσκεται στο «Κατάστιχο των εκκλησιών και μοναστηριών του Κοινού (1248-1548)».

Η εκκλησία βρισκόταν στο χωριό Βασιλειές Τεμένους, κοντά στο Ηράκλειο, και αναφέρεται ως παλαιά και κατεστραμμένη (χωρίς στέγη):«antiqua ecclesia, que vocatur Sanctus Mina; que est dischopetra». Η παρουσία εκκλησίας του αγίου Μηνά στην Κρήτη κατά τους πρώιμους χρόνους της βενετοκρατίας και ο χαρακτηρισμός της ως παλαιάς και κατεστραμένης επιτρέπει σαφώς να θεωρήσουμε ότι τουλάχιστον κατά τη δεύτερη βυζαντινή περίοδο της Κρήτης (961-1204) ο Αιγύπτιος άγιος Μηνάς ήταν γνωστός και ετιμάτο στην Κρήτη. Αν μάλιστα ληφθεί υπόψη ότι ο Νικηφόρος Φωκάς εγκατέστησε στην Κρήτη παλαίμαχους στρατιώτες του, που κατάγονταν κυρίως από την Μ. Ασία, όπου είχε μαρτυρήσει και όπου ιδιαιτέρως ετιμάτο ο άγιος Μηνάς, μπορούμε να υποθέσουμε ότι μέσω εκείνων των μικρασιατών εποίκων έφτασε στην Κρήτη η λατρεία του Αγίου, αν δεν ήταν γνωστή προηγουμένως από την πρώτη βυζαντινή περίοδο.

Στους καταλόγους των εκκλησιών του Χάνδακα κατά την περίοδο της βενετοκρατίας αναφέρεται η εκκλησία της Παναγίας της Παντάνασσας, δίκλιτη, με το άλλο κλίτος αφιερωμένο στον 'Αγιο Μηνά: «S.Maria chivia i Pandanasos; agios Minas, idest S. Menas», «Η Κυρία η Παναγία και ο άγιος Μηνάς». Η μικρή αυτή εκκλησία υπάρχει και σήμερα και πρόκειται για την παλαιά εκκλησία του αγίου Μηνά. Στο βιβλίο του Θ. Δετοράκη «Μηνάς ο Μεγαλομάρτυς» δημοσιεύεται σχέδιο του βενετοκρατούμενου Χάνδακα του Μανέα Κλόντζα όπου σημειώνεται καθαρά η θέση της εκκλησίας ακριβώς εκεί όπου είναι σήμερα, νοτιοδυτικά της μεγάλης μονής της Αγίας Αικατερίνης των Σιναϊτών του Χάνδακα.

Η περιοχή της Αγίας Αικατερίνης των Σιναϊτών του Χάνδακα στο σχέδιο του Μανέα Κλόντζα. Η μικρή εκκλησία άνω δεξιά είναι πιθανότατα η εκκλησία του Αγίου Μηνά.(Το σχέδιο είναι δημοσιευμένο στο Βιβλίο του Θ. Δετοράκη Μηνάς ο Μεγαλομάρτυς,έκδοση Ι.Μ.Ναού Αγίου Μηνά Ηρακλείου.

Αξίζει να τονιστεί ότι η μορφή του αγίου Μηνά εμφανίζεται στις τοιχογραφίες κρητικών εκκλησιών σε πολύ πρώιμη εποχή. Στο βιβλίο του Θ. Δετοράκη «Μηνάς ο Μεγαλομάρτυς» γίνεται αναφορά για την

αρχαιότερη τοιχογραφία που βρίσκεται στον μικρό ναό του αγίου Δημητρίου στο χωριό Πλατανέ Σελίνου (1372-1373μ.Χ). Μια δεύτερη τοιχογραφία βρίσκεται στο ναό της Κοιμήσεως της Θεοτόκου στο χωριό Θρόνος Αμαρίου χρονολογείται από το 1491 ενώ μια τρίτη τοιχογραφία βρίσκεται στο νότιο τοίχο του ναού της Παναγίας στο χωριό Ρουσοσπίτι Ρεθύμνης και χρονολογείται στο 1540μ.Χ.

Ανάμεσα στις λίγες μαρτυρίες των χρόνων της βενετοκρατίας για τον άγιο Μηνά, ιδιαίτερη αξία έχει ένα ιαμβικό επίγραμμα. Το επίγραμμα περιέχεται σε ανέκδοτο ακόμη κρητικό «ιαμβικόν μηνολόγιον» του 17ου αιώνα, ποίημα Ιωάννου του εκ Χάνδακος της Κρήτης. Κατά τον καθηγητή Θ. Δετοράκη στο βιβλίο του «Μηνάς ο Μεγαλομάρτυς» το επίγραμμα αυτό είναι εξαιρετικά ενδιαφέρον μιας και είναι η αρχαιότερη γνωστή μαρτυρία για τη σχέση του αγίου με την Κρήτη και ιδιαίτερα με τον Χάνδακα.