The airline was founded on 19 October 1995 in Bassersdorf, Switzerland, with just one aircraft, a McDonnell Douglas MD-83. The fleet was subsequently expanded and renewed. In 1998, new Airbus A320 aircraft were introduced to replace the MD-83s, and in 1999 long-haul flights were commenced using the Airbus A330-200. As of March 2011, Edelweiss Air added the larger Airbus A330-300 to its fleet, with an order having been filed on 5 April 2010.
Until November 2008, Edelweiss Air was wholly owned by Kuoni Travel Ltd and had 190 employees, when the operating rights were sold to Swiss International Air Lines, in exchange for sale rights of hotel capacities via the Swiss sales network. following Swiss International Airlines being been acquired by the Lufthansa Group in 2005, Edelweiss Air also became a subsidiary of Europe's largest airline group the same time it was acquired by Swiss.