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 were it had been scheduled to land completing a chartered flight from Hassi R'Mel Airport. The pilot Mebarki Mohamed had 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.