The airline traces its origins to an air taxi company Taxi Aéreo Vale do Juruá, established in Cruzeiro do Sul in September 1972. In March 1994 it was transformed into a regional scheduled operator, changed its name to TAVAJ Transportes Aéreos Regulares S/A, and moved its base to Rio Branco. In 2002 TAVAJ moved its base again, this time to Manaus. It ceased its operations in 2004.
In 1999 TAVAJ suffered a hard blow during the currency exchange devaluation crisis. Because of high leasing and insurance costs, the airline was forced to return the 2 Dash 8-200B. Continuous economic difficulties lead TAVAJ to cease passenger operations in 2004.