Theveste was founded by Romans in 75 AD to control the mountain passes.
From Schoder's lecture notes:
THEVESTE (Tebessa): impt. in III c. Seat of Legio III Augusta from 25 BC til transfer to Lambaesis inearly 2 c. AD.
Colony under Hadrian, 30,000 inhabitants.
Temple of Herc.: early 3 c.; had colonnaded court. Exc preservation. Cp. 'Maison Carree'. Museums.
Arch to Caracalla & Geta, 212, at ex[penses of Caius Cornelius Egrilianus, native o fTheveste, later Prefect of 14th Legion in Pannonia, costing 250,000 sesterces. Inscritions on 3 faces, to Caracalla, father Sept. Severus, mother Julia Domna.
X Xn. Basilica, fr. Narthex entry -- late 4 c., one of best in Africa. Fine marbles, mosaics. NB fish.
Hotel for Pilgrims, inside Basilica peribolos cols. 80 rooms, places for horses and chariots.