Arke traces its roots to Air Holland, which was founded in 1981. After financial problems Air Holland was taken over by the Exel Aviation Group and took a new start as HollandExel in March 2004. In May 2005 the Exel Aviation Group was declared bankrupt. The German TUI Group took over the airline's activities and renamed it ArkeFly. It is now wholly owned by the TUI Group. Its name was based on the biggest Dutch tour operator, Arke, which is also a subsidiary of the TUI Group. The newly reorganised airline operated its first flight in September 2005.
Operations in Curaçao, Netherlands Antilles, began on 15 July 2004 as DutchCaribbeanExel, which was originally part of the Exel Aviation Group, but was later taken over, together with parent airline, HollandExel, by TUI Nederland, and renamed ArkeFly Curaçao. ArkeFly started weekly flights to St. Maarten from Amsterdam on December 2, 2007, but discontinued this service in November 2008. TUI Nederland holds that flights may resume if the volume of tourists travelling to St. Maarten increases.