It hosts several historical landmarks, the most important one being the wall that surrounds the city and its gates.

Tebessa, written Tébessa in French, was known to the ancient Greeks as Thebéstē (Θεβέστη) or Hekatompýlē (Ἑκατομπύλη, 'Hundred Gates').

After the establishment of the Roman Empire, the 3rd Augustan Legion was based in Theveste before being transferred to Lambaesis.

Some of its other bishops are known: Romulus in 349; Urbicus in 411; Felix exiled by the Vandals in 484; Palladius mentioned in an inscription.

In June 1918, a Latin codex of 26 leaves written by the Manichaeans was discovered in a cave near the city.

In the 11th century, Banu Hilal, an Arab tribe originally living between the Nile and Red Sea, settled in Tripolitania, Tunisia, and Constantinois (the area around Constantine and Tebessa).