Es va crear per divisió de la Tarraconense a finals del segle iii amb la reorganització de Dioclecià o al principi del segle iv amb Constantí el Gran. El 395 se'n separar Insulae Balearum.[1] La capital inicial fou Cartago Nova, l'actual Cartagena, però en el període visigot era Toledo, ja que Cartago Nova fou ocupada pels romans d'Orient. El nom de la província venia de Cartago Nova. S'estenia per les dues Castelles, Múrcia, Andalusia Oriental (Almeria) i la part sud del País Valencià. Amb els àrabs va canviar de nom a Tolaitola, nom àrab de la capital Toledo. També rep aquest nom la diòcesi amb capital en la ciutat de Cartagena i amb seu catedralícia a Múrcia.
Com assenyala J. Arce, des de la invasió franca cap al 260, i fins l'invasió bàrbara del 409 Hispània va romandre en pau i tot el segle iv va ser per a la península ibèrica un segle de pau i prosperitat, passant sense traumes dignes de menció de mans d'un emperador a un altre, o d'un usurpador a un altre. A mitjan segle iv, possiblement sota Julià II, les illes Balears van ser transformades en la província Balearica, esqueixant-se probablement de la Cartaginense, millor que de la Tarraconense.
La província va patir l'impacte de l'invasió de vàndals, sueus i alans de 409, veient saquejats els seus territoris, especialment els de la Meseta. El 441 el rei sueu Réchila va conquerir les províncies Cartaginense i Bètica. Retornada als romans, la província va tornar a ser saquejada pels sueus en 456. A mitjan el segle v va ser annexada pels visigots dirigits pel seu rei Euric, els qui van mantenir la província com una de les demarcacions del seu regne.
A principi del segle vi, tropes romanes d'Orient van incorporar al domini de Constantinoble en nom de l'emperador Justinià I la zona costanera de la província, i li va sumar part de la Baetica formant una nova província que abastava des de l'Algarve portuguès fins al sud de l'actual província de València. Justinià va canviar el nom de la capital pel de Carthago Spartaria i la va convertir en capital de la província d'Espània.
Gran part dels territoris romans d'Orient van ser reconquerits per al Regne Visigot per Leovigild (568-586). La capital, Carthago Spartaria, encara resistiria alguns anys més, fins a la seva conquesta i destrucció pel rei visigot Suíntila cap a l'any 622. El 711, la invasió musulmana de la Península va suposar la desaparició de la província.
