The airline was established and started operations in July 1999 as a cargo airline, especially for diamond mines. Passenger services were added in February 2002. Due to safety concerns regarding the whole Angolan airline industry, Air Gemini is on the list of air carriers banned in the European Union. In 2010 they entered financial difficulties and reduced operations. 
On the 5 January 2001, an Air Gemini Boeing 727 cargo aircraft (registered S9-BAI) ran off the runway upon landing at Dundo Airport following a flight from Luanda, killing one ground worker. The accident occurred because the airplane had touched the ground short of the runway threshold, resulting in a collapsed landing gear and a subsequent skid-off.