Tassili Airlines was established in 1998 as a joint venture between Air Algérie (49%) and the Sonatrach company (51%). Commercial services were launched on 8 April 1999 with a flight from Hassi Messaoud to Algiers. In 2005 Air Algérie withdrew its funds in the airline, which thus became wholly owned by Sonatrach.
On 28 January 2004 at around 21:00 local time, a Tassili Airlines Beechcraft 1900 (registered 7T-VIN) crashed 10 kilometres short of Ghardaïa Airport where it had been scheduled to land completing a chartered flight from Hassi R'Mel Airport. The pilot Mebarki Mohamed had to abort the landing approach because a preceding aircraft had not cleared the runway in time. During maneuvering for reaching the approach path again, the aircraft hit the ground with its right wing, which was subsequently torn off. Of the two passengers and three crew members on board, all but the co-pilot survived the crash.
A Tassili Airlines Bell 206 was destroyed by impact and post impact fire when it crashed on an empty lot at Dekakna, about 5km southwest of Douera, Algeria on August 10, 2017. All four on board are believed to have died in the accident. The accident happened in daylight (1020L) and apparently in VMC. According to press reports the helicopter was being used to film the new railway line between Zeralda and Algiers.