A Navegação Aérea Brasileira foi lançada em 17 de setembro de 1939 e constituída em 28 de fevereiro de 1940 em uma assembleia, onde a organização apresentou o Sr. Paulo V. da Rocha Vianna como seu presidente. Em 4 de maio seus diretores encomendaram 2 Beechcraft 18 que chegaram de navio ao Rio de Janeiro, a primeira aeronave, o PP-NAA, chegou no navio da Lloyd, Comandante Pessoa, em 27 de novembro de 1940. As outras duas aeronaves, um Beechcraft 18 e um Becchcraf D17, prefixos PP-NAB e PP-NAC, respectivamente, chegaram no início de janeiro de 1941 a bordo do navio Almirante Tamandaré, vindo de New York.
Em 28 de março de 1941 operou sua primeira linha, ligando o Rio de Janeiro a Belo Horizonte, Bom Jesus da Lapa, Petrolina e Recife, antes de ser aprovada as operações da empresa, que deu-se em 5 de maio.
A empresa construiu seu hangar oficina em Manguinhos (RJ), na variante da Estrada Rio – Petrópolis.
Em 6 setembro de 1941 a companhia iniciou uma linha para a capital cearense, Fortaleza, partindo do Rio de Janeiro (Santos Dumont), às 7h30, com escalas em Belo Horizonte – Bom Jesus da Lapa e Petrolina. Em novembro inaugurou uma nova linha, para transporte de malote postal na rota Rio de Janeiro (Santos Dumont) para Recife, com as mesmas escalas do voo para Fortaleza.
Com subsídios do governo, recebidos em 1941 e 1942 a empresa expandiu sua frota comprando 2 Lockheed Loderstar e 1 Stinson Reliant. Em agosto de 1942 a NAB construiu em Petrolina uma estação de rádio, depósitos, hangares, hotel e uma pista de 1.200 metros de extensão. Naquele ano de 1942 a NAB transportou 2.384 passageiros e expandiu serviços para Bom Jesus da Lapa – Petrolina – Teresina e Belém.
Em 1943 suas rotas partiam do Rio de Janeiro (Santos Dumont) para Bom Jesus da Lapa – Teresina e Belém. Também do Rio de Janeiro, partia para Belo Horizonte – Bom Jesus da Lapa – Petrolina – João Pessoa e Recife. Algumas rotas de Petrolina seguiam para Fortaleza, como destino final e outra para Teresina – São Luís e Belém.
Em 1944 e 1945 recebeu novos subsídios do governo e comprou mais 3 Loderstar, um deles chegou em 14 de agosto, o de prefixo PP-NAJ. Em 15 de fevereiro de 1945 perdeu em acidente uma de suas aeronaves, que acabará de decolar de Lagoa Santa para o norte do país. Em novembro de 1945 recebeu seu primeiro Douglas DC-3, prefixo PP-NAK. Em maio de 1946 comprou dois Douglas DC-3, um deles o PP-NAM, foi o penúltimo DC-3 fabricado, e em 23 de janeiro de 1947 recebeu uma terceira aeronave, a PP-NAN, que chegou no Aeroporto Santos Dumont.
Com a criação desenfreada de inúmeras empresas no pós guerra, várias empresas competiam entre si e contra as empresas tradicionais e a NAB, que já não ia nada bem, ficou ainda pior. A empresa ligava Rio de Janeiro e São Paulo a cidades do Nordeste brasileiro, mas com muita competição.
Nos seis primeiros meses de 1948 seus funcionários ficaram sem receber seus salários. Em 17 de agosto de 1948 a empresa suspendeu suas operações e deixou aviões parados e 600 empregados sem receber.
Em novembro de 1948 o governo instituiu uma comissão para analisar a situação administrativa e financeira da NAB para propor um plano de reorganização da empresa. O plano foi entregue ao Ministério da Fazenda em junho de 1949. Em 28 de dezembro de 1950 arrendou os Douglas DC-3 de prefixos PP-NAL e PP-NAN para a Linha Aérea Transcontinental Brasileira e o outro passou a voar entre o Rio de Janeiro, Montes Claros, Governador Valadares e Vitória, em linha iniciada em janeiro de 1951. O PP-NAL sofreu um acidente em junho de 1951, quando arrendado a Transcontinental.
Em 1954 a situação da empresa era muito grave e Dilvo Peres, juntamente com a Panair do Brasil, começaram a reerguer a empresa. Houve momentos que operou somente entre o Rio de Janeiro e Cachoeiro do Itapemirim! Em 1957 a empresa adquiriu 2 Curtiss C-46 e passou por total reestruturação. Em 1958 comprou 10 Douglas DC-3 da Panair do Brasil, com a qual realizou acordo operacional e passou a operar as linhas para Recife, transferidas pela Panair.
Em 1960 adquiriu mais 9 Curtiss C-46 e passou a operar vôos noturnos e mais baratos. Em 24 de outubro de 1961 a NAB foi comprada pelo Loide Aéreo Nacional, que posteriormente foi adquirido pela VASP.
