The airline was established in early 2005 by Cpt. Miltiadis Tsagkarakis, a former Olympic Airlinesdirector-general and pilot as well as George Mavrantonakis, former Chief Operating Officer and Accountable Manager of Olympic Airlines and former Advisor to the President of Olympic Airways. Operations commenced in July 2005, including scheduled, charter and cargo flights, air-taxi, emergency medical services, excursions and sightseeing. Sky Express Aircargo was later established in a joint effort with the Finaval Group, focusing on cargo transport between Europe and the Far East.
The airline's initial logo was inspired by the flag of the Cretan State, a semi-independent state under the Ottoman Empire. The flag of the Cretan State was composed of a white cross extending to the edges of the flag, with the upper-hoist canton in red, featuring a white star symbolizing Ottoman sovereignty on the island, and the other squares in blue, symbolizing the Greeks of Crete. The flag has also been adopted as the flag of the Cretan independence movement recently. The logo was not well-received, and following complaints by the public in Greece, especially Cretans, the logo was changed. The company has said that they do not consider the flag to be offending, since it represented a milestone in the Cretan unification with the Kingdom of Greece, but changed their logo anyway in order to avoid any further confusion.
On 12 February 2009 a BAe Jetstream 31 registered SX-SKY experienced a right main gear collapse after landing inbound from Rhodes. None of the 15 passengers and 3 crew were injured, but the aircraft sustained considerable damage to its right landing gear, wing and propeller that was deemed beyond economical repair, resulting in the aircraft being written-off. The cause of the accident was that the aircraft had previously suffered two heavy landings in the previous 27 which were not reported. One of the heavy landings caused a fracture in a landing gear cylinder, which propagated until the cylinder failed, causing the landing gear to collapse. SX-SKY was noted being scrapped at Heraklion airport in late February 2011.
On 2 February 2015 a Jetstream 41 aircraft registered SX-DIA, operating flight GQ-100 from Heraklion experienced a left main gear collapse and runway excursion after landing hard on Rhodes due to strong winds. None of the 16 passengers or 3 crew were injured. The aircraft received substantial damage.