Air Atlantis was a charter operations wholly owned by TAP-Air Portugal and began operations in May 1985 using a Boeing 707 and a Boeing 737-200 aircraft. In 1986 the Boeing 737 was replaced with two Boeing 727-100 and the Boeing 707 with three Boeing 727-200s, which were the first aircraft painted in the new airline's livery. The 727s were replaced by Boeing 737-200 and leased brand new Boeing 737-300 from 1988 onwards. By 1993, TAP-Air Portugal decided to restructure its operations and Air Atlantis was dissolved at the End of April 1993.
Charter flights were flown from Amsterdam, Stockholm, Bristol, Brussels, Copenhagen, Düsseldorf, Exeter, Frankfurt, Glasgow, Hamburg, London, Manchester, Munich, Newcastle, Stuttgart and Zurich to points in Portugal, but mostly Faro.