The airline began operations on August 25, 1995 with a Boeing 727-200 as a charter carrier linking Rio de Janeiro and São Paulo to holiday destinations in the northeast of Brazil. Originally it was a direct competitor of Air Vias, another Brazilian airline dedicated to charter flights. Eventually Fly became a carrier with both charter and scheduled low-cost operations.
Though successful in its first years, it suffered a hard economic blow during the 1999 currency exchange devaluation crisis, and a great decrease in traffic, following a world trend, in the second semester of 2001. Those difficulties lead to increasing administrative difficulties. The final blow came with increasing competition with Gol Airlines which lead to the ceasing of operations in 2003.