Midwest Airlines was founded in 1998 with an initial fleet of two Airbus A310-300s. Of those, one was sold in 2004, while the other one is stored.
From its beginning, the airline offered charter services from Egyptian holiday resorts to Europe and the Middle East on behalf of local and international tour operators. Due to circumstances attributable to the then owners, the airline stopped operations in 2006. The sale of the company was formalized in May 2009, followed by more acquisitions of shares, and a restructuring and reorganization of the company was effectively started in September 2009. Concerted efforts during 2009 brought Midwest back into the air operations scene. A Boeing 737–800 was dry leased, which enabled the airline to renew its AOC.