O topónimo mais antigo que se conhece da área é Mastia, que tradicionalmente se identifica com a cidade nos períodos ibero ou tartéssico. Os Fenícios fundaram uma colónia com o nome de Qart Hadašt ("nova cidade"), o mesmo que tinham dado a Cartago. Durante a época romana chamou-se, em latim, Carthago Nova. O acusativoCarthaginem deu origem ao nome árabeقرطجانة (Qarṭaǧānatu), a forma que precedeu a atual, Cartagena.