A aviação comercial começou na área de Norfolk por volta de 1926. Os cidadãos de Norfolk voaram comercialmente pela primeira vez na Linha Mitten. Era administrada pela Philadelphia Rapid Transit Air Service, Inc. (Filadélfia Rapid Transit Air Service, Inc.). O Aeroporto Internacional de Norfolk foi construído em 1938. Tinha uma pista de 3.500 pés (1.100 m). O primeiro terminal foi construído em 1940.
Durante a Segunda Guerra Mundial, o Aeroporto Municipal de Norfolk tornou-se importante para o esforço de guerra. O Corpo Aéreo do Exército dos Estados Unidos tomou o controle do aeroporto entre 1942-1947. Eles tornaram a pista mais longa e construíram duas outras pistas de decolagem. Isto foi feito para lidar com um número muito maior de vôos e aeronaves maiores. A Ala de Caças de Norfolk foi criada em agosto de 1942. Ele fornece defesa aérea para a área de Norfolk. O 52d Fighter Group foi colocado no aeroporto após o ataque a Pearl Harbor, em dezembro de 1941. Muitos esquadrões estiveram no aeroporto de Norfolk durante os primeiros anos da guerra. Isto terminou no final de julho de 1944.
O Corpo Aéreo do Exército deu o controle do aeroporto de volta à cidade no final de 1945. A quantidade de viagens comerciais cresceu rapidamente, com duas novas companhias aéreas tendo vôos regulares. Em 1948, a Piedmont Airlines iniciou vôos. Nesse mesmo ano, começou a construção de um terminal maior e mais moderno.
Em 1950, o controle do aeroporto foi entregue à recém-criada Autoridade Portuária e Industrial de Norfolk (NPIA). Naquela época, o Aeroporto Municipal de Norfolk era um dos mais movimentados do país. Em 1951, o novo terminal foi inaugurado.
Nos anos 60, ocorreu a mudança de aviões a hélice para jatos. O Aeroporto Municipal de Norfolk fez mudanças com pistas mais longas e fortes e instalações de taxiway. Por causa disso, em 1968, o aeroporto foi o centro de transporte aéreo para toda a área das estradas de Hampton. Seu nome foi mudado para Aeroporto Regional de Norfolk. Para estar pronta para um grande crescimento nas próximas três décadas, a NPIA criou um plano que iria fazer crescer o aeroporto ao entrar no século 21.
Em 1974, o aeroporto abriu seu novo terminal. Mais terrenos foram comprados para que o aeroporto pudesse ser ampliado. Em 1976, o nome do aeroporto foi mudado para Aeroporto Internacional de Norfolk. Foram acrescentadas as instalações aduaneiras federais. Novos prédios foram construídos para abrigar o posto de bombeiros, o depósito de manutenção e a torre ATC. Um dos problemas que o aeroporto enfrentou ao crescer foi resolvido pelo Jardim Botânico vizinho. Ele criou uma área de amortecimento entre o aeroporto e a cidade ao seu redor. O Aeroporto Internacional de Norfolk foi cercado pela beleza durante todo o ano. Era um modelo nacional para lidar com as crescentes instalações aéreas e um santuário ecológico.
Nos anos 80, muitas mudanças aconteceram. Uma nova instalação de aviação geral foi inaugurada. Um novo terminal de carga aérea também foi construído. Mais áreas para estacionamento também foram acrescentadas. Até mesmo o nome do órgão controlador mudou em 1988 - de Norfolk Port and Industrial Authority para Norfolk Airport Authority.
Nos anos 90, o terminal de carga aérea e as instalações de estacionamento foram ampliadas. Em 1991, a Norfolk International ampliou os concursos. Isto acrescentou 10 portões adicionais. Agora tinha um total de 24 portões. Um novo posto de bombeiros e novas instalações de torres de controle de tráfego aéreo da FAA também foram construídas.
