Its services started on 25 June 1976 and its operational area comprised roughly the Northeast and parts of the Southeast regions of Brazil, specifically the states of Piauí, Ceará, Rio Grande do Norte, Paraíba, Pernambuco, Alagoas, Sergipe, Bahia and parts of Maranhão, Minas Gerais, and Espírito Santo plus the possibility of serving the cities of Rio de Janeiro, São Paulo, and Brasília when linking them to its area of concession.

Finally, in 2002, the administration of Varig, Rio-Sul, and Nordeste was unified, although the Ruben Berta Foundation kept the three brand names independent.

[7] Between 17 June 2005 and 2 September 2009, Viação Aérea Rio-Grandense, operator of the brand Nordeste and later Flex, remained in Recovery Order in the 1st Business Court of Rio de Janeiro, under the leadership of Judges Luiz Roberto Ayoub and Miguel Dau.

Since bankruptcy protection was lifted, the administration of the airline returned to its original owner, Fundação Ruben Berta.

[10] On November 10, 2009, the director Aurélio Penelas was replaced by Carlos Berardinelli, who was able to reach an agreement with the lessor weeks later.

[12][13] Nordeste Linhas Aéreas Regionais operated services (in its own right) to the following domestic scheduled destinations (in January 2005): Porto Seguro, Salvador and São Paulo.