G. Mokhtar places it just within the Roman province of Africa Proconsularis, to the east of Numidia, but it is generally believed to have been in Numidia, a province created probably in 198–199.
Calama was founded by the Phoenicians and called Malaka, similar to their colony Malake (Punic: 𐤌𐤋𐤊𐤀, MLKʾ) at Málaga, Spain. Malaka was situated in the Berber kingdom of Numidia. When this area later came under Roman rule, the city was renamed Calama. Between the late republic and early empire, it was governed by a Punic-inspired twin magistracy of sufetes.
Whether Calama is identical with the town of Suthul which the Roman general Aulus Postumius Albinus unsuccessfully tried to take in 110 BC, (cf. Battle of Suthul) is disputed, with some denying and others cautiously affirming.
In the 1st century AD, Calama, then part of the Roman province of Numidia, became a major urban centre. It was given the rank of a Roman municipium as early as Hadrian, and of a colonia later. The city was sponsored by Vibia Aurelia Sabina, sister of the Emperor Commodus (late 2nd century). Calama was, with Setifis (Setif) and Hippo Regius (Annaba), one of the granaries of Rome in the 2nd and 3rd centuries AD. Under Septimius Severus, Calama became one of the most prosperous in the Roman empire, with thermae and a huge theatre.
Calama became a Christian bishopric, four of whose bishops are named in extant documents:
Possidius wrote the first biography of Augustine, in which he lets it be known that he himself was one of the clergy of Augustine's monastery when he was appointed bishop of Calama. When Calama fell into the hands of the Vandal king Genseric in 429, Possidius took refuge with Augustine within the walled city of Hippo Regius. He was present at Augustine's death in 430.
After the conquest of Numidia by the Byzantine Empire, Solomon (a general of Justinian I) built a fortress there between 539 and 554. Calama's population was fully Christian in the 6th and 7th century.
With the spread of Islam, Byzantine rule of Calama ended (some Christians survived until the 9th century) and slowly Calama disappeared around the 11th century (see Guelma).