Mέχρι το 1956, κάπου 30 χρόνια μετά την ίδρυση του, η δραστηριότητα του O.Φ.H. περιοριζόταν στο τοπικό πρωτάθλημα της A’ κατηγορίας Hρακλείου (EΠΣH), γιατί δεν είχε κατορθώσει να προκριθεί στην τελική φάση των προκριματικών που θα του επέτρεπαν να διεκδικήσει την συμμετοχή του στο Eθνικό Πρωτάθλημα. Οι πρωταθλήτριες ομάδες της Ελληνικής επαρχίας έπρεπε να δώσουν κι άλλους αγώνες μπαράζ για να πάρουν το εισιτήριο για την τελική φάση.
Tα πράγματα άλλαξαν την σεζόν 1955-1956. Μετά το πέρας των πρωταθλημάτων των τριών μεγάλων Ενώσεων, έγιναν τρεις προκριματικοί όμιλοι. Ο Ο.Φ.Η. ως πρωταθλητής της Ε.Π.Σ. Ηρακλείου, μετείχε στον Νότιο όμιλο, όπου είχαν τοποθετηθεί οι δυο πρώτοι της Ε.Π.Σ. Πειραιά (Ολυμπιακός, Εθνικός), ο Ολυμπιακός Λουτρακίου (ΕΠΣ Αργολιδοκορινθίας) και η Παναχαϊκή (ΕΠΣ Αχαϊας). Ο Ο.Φ.Η. σε εκείνη τη συμμετοχή του δεν τα κατάφερε.
1956-1957
Μετά το τέλος των τοπικών πρωταθλημάτων και για τη συμπλήρωση των δυο θέσεων της τελικής φάσης του Εθνικού πρωταθλήματος, δημιουργήθηκαν δυο όμιλοι (Νότιος – Βόρειος) με τη συμμετοχή μόνο επαρχιακών ομάδων.
Ο Ο.Φ.Η. ως εκπρόσωπος της ΕΠΣ Ηρακλείου τοποθετήθηκε στον Νότιο όμιλο και είχε για αντιπάλους την Παναχαϊκή, τον Ολυμπιακό Χαλκίδας και τον Παναργειακό. Κατέλαβε την τρίτη θέση της γενικής κατάταξης.
1957-1958: Ό,τι δεν είχε πετύχει ο Ο.Φ.Η. τα δυο προηγούμενα χρόνια, το κατάφερε στην τρίτη συμμετοχή του. Αφού ξεπέρασε με επιτυχία τη δοκιμασία των προκριματικών έπαιξε στη συνέχεια στο Εθνικό πρωτάθλημα, τερματίζοντας στη 12η θέση.
1958-1959
Ήταν η τελευταία χρονιά που η ΕΠΟ διοργάνωσε το Εθνικό πρωτάθλημα, καθώς από την αγωνιστική περίοδο 1959-60 θεσπίστηκε το πρωτάθλημα της Α’ Εθνικής.
Ο Ο.Φ.Η. δεν κατάφερε να διεκδικήσει μια θέση στο νέο πρωτάθλημα, καθώς στους αγώνες της προκριματικής φάσης, νίκησε μόνο μια φορά.
Πριν όμως ξεκινήσει η Α’ Εθνική η «τύχη» χτύπησε την πόρτα του ΟΦΗ για δεύτερη φορά. Και να πως…
Το πρωτάθλημα της Α’ Εθνικής αποφασίστηκε να γίνει οπωσδήποτε! Αν και ήδη είχαν αρχίσει τα τοπικά πρωταθλήματα, η ΕΠΟ πήρε την τελική απόφαση: 10 Οκτωβρίου αρχίζει η Α’ Εθνική. Όμως έπρεπε να συμπληρωθεί σε πανελλήνια κλίμακα, ο αριθμός των 16 σωματείων. Έτσι έβαλε να παίξουν οι δυο οι νικητές των δυο υποομίλων της περσινής διοργάνωσης και στη συνέχεια ο νικητής θα αντιμετώπιζε την Προοδευτική, ενώ στον Βορρά ο Ηρακλής Θεσσαλονίκης θα έπαιζε με την Ασπίδα Ξάνθης (1-0, 2-0).
Κι εδώ ήταν που ο Ο.Φ.Η. έχασε για δεύτερη φορά την ευκαιρία. Ηττήθηκε με σκορ 2-1 στην Χαλκίδα από τον Ολυμπιακό, τον νίκησε με 2-1 στο Ηράκλειο, αλλά στο τρίτο ματς έχασε 1-0 και έτσι δεν αντιμετώπισε την Προοδευτική, που χρειάστηκε τρία ματς (2-2, 0-0, 3-0) για να ξεπεράσει τον Ολυμπιακό Χαλκίδας και να μπει αυτή στην Α’ Εθνική.
