Οι κατασκευαστικές εργασίες αρχίζουν το 1932, αλλά σταματούν τον επόμενο χρόνο, κυρίως λόγω έλλειψης κονδυλίων. Από τις αρχές του 1937 οι εργασίες ξαναρχίζουν και στις 12 Μαρτίου του 1939 το αεροδρόμιο Ηρακλείου παραδίδεται «προς χρήσιν». Στις 8.30 π.μ. της 19ης Μαρτίου αεροσκάφος τύπου Junkers Ju 52 της Ελληνικής Εταιρίας Εναέριων Συγκοινωνιών, με πιλότο τον Ιωάννη Τσούκα, φτάνει στο Ηράκλειο. Είναι το πρώτο που προσγειώνεται στο νέο αεροδρόμιο μπροστά σε δεκάδες Ηρακλειώτες, που έχουν σπεύσει να παρακολουθήσουν το γεγονός.
Τα επίσημα εγκαίνια της αεροπορικής γραμμής Αθηνών - Ηρακλείου πραγματοποιούνται στις 13 Απριλίου 1939 παρουσία του νομάρχη Ανδρέα Μάρκελλου και του δημάρχου Μηνά Γεωργιάδη. Από τον Αύγουστο του ίδιου χρόνου εκτελούνται πλέον τακτικά τρεις εβδομαδιαίες πτήσεις Αθήνα-Ηράκλειο που εξυπηρετούν τη μεταφορά επιβατών, ταχυδρομικής αλληλογραφίας και εμπορευμάτων.