It is hard to imagine that the site where the Carthaginian general Hasdrubal the Fair would found a new city, Carthago Nova, was uninhabited. It has one of the best protected ports in the Mediterranean and was close to a silver mine. It is possible that it was the area of a placed called Mastia, mentioned in several sources in about this part of the Iberian coast.
However that may be, from about 228 BCE, Hasdrubal used this port, which he named after Carthage itself Kart hadašt ("new city") as base for the exploitation of Iberia. The products of the silver mines must have passed through this city, which boasted sanctuaries for Ba'al and Eshmun. It was also a storage of arms, a palace, a garrison, and the place from which Hannibal Barca started his march to Italy in 218 BCE.
While Hannibal was waging war in Italy, the Romans conquered Iberia. This proved harder than they had suspected. After some initial successes, the Roman generals were killed in action and almost all was lost. However, a young commander, Publius Cornelius Scipio, took Carthago Nova by surprise (in 209) and brought the Spanish war to a good end in 206. He was to defeat Hannibal at Zama in 202.
In the Roman world, the port remained important. In 44 BCE, it was the third city in Iberia after Tarraco and Corduba, and was elevated to the rank of colonia, which meant that all free-born, male citizens received Roman citizenship. The official name was Colonia Urbs Julia Nova Carthago. The emperor Augustus (r.27 BCE - 14 CE) gave the city a theater and a new forum. The city would also be one of the juridical districts of the province of Hispania Tarraconensis. It retained a Carthaginian flavor, though: Punic inscriptions were still cut in the first century CE.
In 297 or 298, the emperors Diocletian and Maximian reorganized Iberia and created a new province, Hispania Carthaginensis, with Carthago Nova as capital. In the fifth century, the western part of the Roman Empire disintegrated. In 422, the city was captured and sacked by the Vandals before passing from there to Africa.
After the Vandal sack of Rome (455), the Visigoths, officially fighting for the emperor Avitus, conquered large parts of the Iberian peninsula, including Carthago Nova. In 461, the emperor Majorian tried to reconquer the city, but the Roman navy was defeated and destroyed. The city remained part of the Visigothic kingdom.
After the mid-sixth century, it became Byzantine, and remained so until 622, when the Visigothic king Suintila captured and destroyed the city, which barely survived. Ecclesiastical life, however, continued; a bishop from Carthago Nova was one of the signatories of the acts of the Eleventh Council of Toledo (575). The city was conqured by the Arabs in 711.