The airline was established in 2005 albeit under a different name, Nordic Solutions Air Services. The main purpose of the company at the time was to operate charter and wet lease flights on SAAB 340 cargo and passenger aircraft. The company grew steadily to a size of four SAAB 340 aircraft operating mostly in Northern Europe for integrator bluechip clients such as TNT, DHL and Royal Mail. In 2008 the company was re-branded to its current name Avion Express.
In 2010 Avion Express was acquired by French investment company Eyjafjoll SAS, formed by Avion Capital Partners of Switzerland along with strategic investors from industry. The new owners set up a long term plan to develop the airline as an ACMI specialist. The first step of this plan was to move towards a jet airplane operation. A significant milestone was reached in April 2011 when Avion Express introduced its first Airbus 320 passenger aircraft. The aircraft was based in Milan, Malpensa and operated on behalf of Italian tour operators throughout the summer season.
During 2012 and 2013 more aircraft were added and by summer 2014 Avion Express operates a fleet of 9 Airbus A320 and 2 Airbus A319. In 2013 Avion Express successfully passed the IOSA Operational Safety Audit and consequently obtained an IATA registration. The last Saab 340 Cargo aircraft was removed from operation in March 2013. There are about 50 staff in the Vilnius headquarter.