Carthago Nova is in de 3e eeuw v. Chr. gesticht door Hasdrubal de Schone, een legeraanvoerder uit Carthago. De stad werd Qart chadast (Nieuwe Stad) genoemd, net als Carthago.
Oorspronkelijk was Carthago een Phoenicische kolonie of nederzetting, toen de oorspronkelijke Phoenicische plaatsen als Tyrus, Sidon en Byblos echter overheerst werden door andere volkeren, begon het evenwicht van de Phoenicische cultuur en de Phoenicische machtssfeer sterk naar het westen van de Middellandse Zee te verschuiven, met Carthago als nieuw centrum hiervan. Cartagena was onderdeel van de verdere verbreiding van deze invloedssfeer naar het westen toe.
In 232 v. Chr. veroverden de Romeinen de stad, en ging het onder de naam Carthago Nova (Nieuw Carthago) deel uitmaken van het Romeinse Rijk. Hiervan is ook de naam Cartagena afgeleid. Dus etymologisch gezien is in de naam 'Carthago Nova' zowel het woord nieuw in het Punisch, als in het Latijn aanwezig, wat dubbelop kan lijken, maar het niet is, want het Latijnse 'nova' werd toegevoegd om het te onderscheiden van Carthago in Noord-Afrika.
Cartagena heeft een archeologisch museum waarin vooral veel opgravingen uit de Romeinse tijd te zien zijn.
Pas recentelijk is er voor de stichter van de stad, Hasdrubal de Schone, een beeld opgericht.
