Η εμπορική αεροπορία ξεκίνησε στην περιοχή του Νόρφολκ περίπου το 1926. Οι πολίτες του Νόρφολκ πραγματοποίησαν εμπορικές πτήσεις για πρώτη φορά με τη Mitten Line. Το δρομολόγιο διηύθυνε η Philadelphia Rapid Transit Air Service, Inc. Το διεθνές αεροδρόμιο του Νόρφολκ κατασκευάστηκε το 1938. Είχε διάδρομο προσγείωσης και απογείωσης 1.100 μέτρων (3.500 πόδια). Ο πρώτος τερματικός σταθμός κατασκευάστηκε το 1940.
Κατά τη διάρκεια του Β' Παγκοσμίου Πολέμου, το Δημοτικό Αεροδρόμιο του Νόρφολκ έγινε σημαντικό για την πολεμική προσπάθεια. Το Σώμα Αεροπορίας του Στρατού των Ηνωμένων Πολιτειών ανέλαβε τον έλεγχο του αεροδρομίου μεταξύ 1942-1947. Κατέστησαν τον διάδρομο προσγείωσης μακρύτερο και κατασκεύασαν άλλους δύο διαδρόμους προσγείωσης. Αυτό έγινε για να αντιμετωπιστεί πολύ μεγαλύτερος αριθμός πτήσεων και μεγαλύτερα αεροσκάφη. Τον Αύγουστο του 1942 δημιουργήθηκε η Πτέρυγα Μαχητικών του Νόρφολκ. Αυτή παρείχε αεράμυνα για την περιοχή του Νόρφολκ. Η 52η Ομάδα Μαχητικών τοποθετήθηκε στο αεροδρόμιο μετά την επίθεση στο Περλ Χάρμπορ τον Δεκέμβριο του 1941. Πολλές μοίρες βρίσκονταν στο αεροδρόμιο του Νόρφολκ κατά τα πρώτα χρόνια του πολέμου. Αυτό έληξε στα τέλη Ιουλίου του 1944.
Το Σώμα Αεροπορίας Στρατού έδωσε τον έλεγχο του αεροδρομίου πίσω στην πόλη στα τέλη του 1945. Ο όγκος των εμπορικών ταξιδιών αυξήθηκε γρήγορα με δύο νέες αεροπορικές εταιρείες να πραγματοποιούν τακτικές πτήσεις. Το 1948, η Piedmont Airlines ξεκίνησε πτήσεις. Την ίδια χρονιά, άρχισε η κατασκευή ενός μεγαλύτερου, πιο σύγχρονου κτιρίου τερματικού σταθμού.
Το 1950, ο έλεγχος του αεροδρομίου περιήλθε στη νεοσύστατη Λιμενική και Βιομηχανική Αρχή του Νόρφολκ (NPIA). Εκείνη την εποχή, το Δημοτικό Αεροδρόμιο του Νόρφολκ ήταν ένα από τα πιο πολυσύχναστα αεροδρόμια της χώρας. Το 1951 εγκαινιάστηκε ο νέος τερματικός σταθμός.
Τη δεκαετία του 1960, πραγματοποιήθηκε η αλλαγή από τα αεροσκάφη με έλικες στα αεριωθούμενα αεροσκάφη. Το Δημοτικό Αεροδρόμιο Norfolk έκανε αλλαγές με μεγαλύτερους και ισχυρότερους διαδρόμους και τροχοδρόμους. Εξαιτίας αυτού, το 1968, το αεροδρόμιο ήταν το κέντρο αερομεταφορών για ολόκληρη την περιοχή Hampton Roads. Το όνομά του άλλαξε σε Περιφερειακό Αεροδρόμιο του Νόρφολκ. Για να είναι έτοιμο για μεγάλη ανάπτυξη τις επόμενες τρεις δεκαετίες, το NPIA δημιούργησε ένα σχέδιο που θα μεγάλωνε το αεροδρόμιο καθώς εισερχόταν στον 21ο αιώνα.
Το 1974, το αεροδρόμιο εγκαινίασε το νέο του τερματικό σταθμό. Αγοράστηκε περισσότερη γη για να μεγαλώσει το αεροδρόμιο. Το 1976, το όνομα του αεροδρομίου άλλαξε σε Διεθνές Αεροδρόμιο Norfolk. Προστέθηκαν ομοσπονδιακές τελωνειακές εγκαταστάσεις. Χτίστηκαν νέα κτίρια για να φιλοξενήσουν τον πυροσβεστικό σταθμό, την αποθήκη συντήρησης και τον πύργο ελέγχου εναέριας κυκλοφορίας. Ένα από τα προβλήματα που αντιμετώπισε το αεροδρόμιο καθώς μεγάλωνε, αντιμετωπίστηκε από τον κοντινό Βοτανικό Κήπο. Δημιούργησε μια ρυθμιστική περιοχή μεταξύ του αεροδρομίου και της πόλης γύρω από αυτό. Το Διεθνές Αεροδρόμιο του Νόρφολκ περιβαλλόταν από ομορφιά όλο το χρόνο. Ήταν ένα εθνικό πρότυπο για την αντιμετώπιση των αναπτυσσόμενων αεροπορικών εγκαταστάσεων και ένα οικολογικό καταφύγιο.
Στη δεκαετία του 1980, έγιναν πολλές αλλαγές. Άνοιξε μια νέα εγκατάσταση γενικής αεροπορίας. Χτίστηκε επίσης ένας νέος τερματικός σταθμός αεροπορικών εμπορευμάτων. Προστέθηκαν επίσης περισσότεροι χώροι στάθμευσης. Ακόμη και το όνομα του φορέα ελέγχου άλλαξε το 1988 - από Norfolk Port and Industrial Authority σε Norfolk Airport Authority.
Τη δεκαετία του 1990 ο τερματικός σταθμός αερομεταφορών και οι εγκαταστάσεις στάθμευσης έγιναν μεγαλύτερες. Το 1991, η Norfolk International διεύρυνε τις αίθουσες αναμονής. Έτσι προστέθηκαν 10 επιπλέον πύλες. Τώρα είχε συνολικά 24 πύλες. Κατασκευάστηκε επίσης ένας νέος πυροσβεστικός σταθμός και νέες εγκαταστάσεις πύργου ελέγχου εναέριας κυκλοφορίας της FAA.
