During the 2000s, AeroSur renewed and expanded its fleet, introducing larger aircraft of the types Boeing 747, Boeing 757 and Boeing 767, which made the inauguration of long-haul flights possible. When Lloyd Aéreo Boliviano went bankrupt in 2007, AeroSur became the largest airline of Bolivia and the only one with intercontinental flights (to Central and North America as well as to Europe). Since 2009, the domestic fleet of ageing 727s is replaced by more modern, though second-hand purchased Boeing 737 Classic airliners.
The subsidiary dubbed AeroSur Paraguay was planned to operate two Boeing 737-200 aircraft of mainline AeroSur. The further development of the project was postponed in mid-2009 pending Paraguayan governmental approval, and later deferred indefinitely.
On 31 March 2012, the airline suspended operations because of unpaid taxes, but resumed all flights on 6 April except for its Madrid route. AeroSur had used a 747 leased from Virgin Atlantic on that route but had returned it to the lessor. The airline plans to resume that route with an ex-Aerolineas Argentinas 747-400. Since then AeroSur has struggled to keep its operations running smoothly and returned its 767 aircraft to the lessor.
On 17 May 2012 AeroSur suspended all its flights again, and other airlines such as state-owned Boliviana de Aviación have since began to fill the void left by AeroSur. The airline is in talks with potential US investor William Petty who has signed a memorandum of understanding to invest up to US$15 million in the Bolivian carrier. AeroSur's air operator's certificate was revoked on 20 July 2012. A group of former employees, as well as William Petty, plan to create a new airline called TU Aerolínea.
AeroSur did not operate any dedicated cargo aircraft, but used the cargo holds of its passenger aircraft for network-wide freight transport. Additionally, tourist sightseeing flights were offered on a single Douglas DC-3.