Em 18 de dezembro de 1939, o governador Benedito Valadares inaugurou o Aeroporto Governador Valadares. A primeira empresa aérea a operar foi a Panair do Brasil, em 1942, ligando Montes Claros à Belo Horizonte, Salvador e Recife, ano em que iniciaram os serviços do correio aéreo postal. Em 1948, a Nacional Serviços Aéreos inaugurou sua atividade com vôos diários no percurso de montes Claros/Belo Horizonte nos aviões DC-3 com capacidade para 24 passageiros. Em 1957, a Nacional foi incorporada à Real Serviços Aéreos.

Em 1965, a Varig assumiu as linhas da Panair do Brasil, e Montes Claros passou a ser servida por aviões AVRO com capacidade para transportar 40 passageiros. Em 1974, a Varig implanta a era do jato em Montes Claros, com o Boeing 737, com capacidade para transportar 109 passageiros e mais de seis toneladas de bagagem e carga.

Em 1977, as atividades da Varig foram temporariamente suspensas, porque a pista não era adequada ao Boeing 737 – aeronave que quando carregada chega a atingir até 50.000 quilos. Foi realizada uma reforma na estrutura da pista, aumentada para 2.100 metros. A estrutura foi reforçada, o que permitiu o retorno das operações. No mesmo ano a Nordeste Linhas Aéreas se instala em Montes Claros, ligando a cidade com vôos regulares para Belo Horizonte e cidades baianas como Salvador, Guanambi e Vitória da Conquista. Em 1980, o Aeroporto passou a ser administrado pela Infraero.

Em 31 de outubro de 2004 a Varig realizou seu último vôo no norte de Minas, após 27 anos de atuação na região. A TRIP Linhas Aéreas que já atuava desde 1º de dezembro de 2001, passou a ser a única a explorar a rota para a Capital mineira, ampliando o número de vôos. Em 29 de novembro de 2004 a Oceanair começou a operar com vôos diários fazendo a linha Montes Claros/São Paulo e encerrou suas operações em 28/05/2010. Em 01/11/2010, a Gol Linhas Aéreas começou suas operações com vôos diários para o Aeroporto Internacional Tancredo Neves e, em 15 de março de 2012, foi a vez de a Azul Linhas Aéreas iniciar suas atividades, com vôos diários também para o Aeroporto Internacional Tancredo Neves.