Los historiadores no manejan una referencia común de los orígenes de Cartagena. Varias personas como Fray Leandro Soler, P. Morote y José María Álvarez, se hacen eco poético de un príncipe troyano, Teucro, que arribó a estas costas, en el siglo XII a. C., a raíz de la desaparición de su ciudad:
Oh dioses, largo ha sido nuestro camino. Y mirando hacia el fin de las aguas, vio la gran llanura que altas montañas guardan, y se le apareció Afrodita y dijo: Oh, Teucro, mira la tierra prometida donde olvidaréis a Troya. Vuestro errar ha terminado. Y Teucro dijo: Moraremos aquí.
Pero es Costa quien le da aún más antigüedad, haciéndola contemporánea de Sagunto, remontándose al siglo XIV a. C. Lo que sí es seguro es que, en el siglo VI a.C., Cartagena ya estaba incluida en los itinerarios de fenicios y griegos.
Sin duda alguna, la mayoría de estudiosos se remontan a los siglos V o VI a. C. para hablar del origen de la Ciudad Portuaria siendo, lo más probable, los Massianos, colonizadores íberos de la Tracia en sus primeras emigraciones desde Asia, los que habitasen Cartagena por primera vez.
Los Massianos fueron denominados por Hecates y Polibio como Mastianos; Herodoto los llamó, Mastienos; Livio Melesmos y Strabón, Bastetanos; y el Doctor Fernández Guerra indica que procedían de un pueblo Massieno que tuvo su cuna en Asia entre el Indo y Ganges y que al llegar a España se extendieron desde Jaén a Bogana y desde el picacho de Veleta al confín de las provincias de Murcia y Alicante. Estos crearon un Estado y lo dividieron en dos partes presididas por dos ciudades que concentraban el poder y la riqueza.
La Tartessia Citerior tenía como capital a Mastia, que según Schulten, Altamira, Costa y otros autores estuvo en la actual Cartagena, encaramada en el Cerro del Molinete, cuyos dominios alcanzaban los ríos Guadiana y Segura. La denominación Mastia deriva de la forma líbica amezda o mazta, que significa lugar de habitación, lugar habitado, población.
La primera descripción de la ciudad de Mastia aparece en la obra “Ora marítima”, también conocida como "Las costas marítimas", del poeta latino Rufo Festo Avieno del siglo IV d. C., aunque para su redacción utilizó fuentes supuestamente más antiguas, como un posible periplo masaliota del siglo VI a. C. Dicha descripción dice así:
... Se halla luego el puerto Namnatio que desde el mar abre su curva cerca de la ciudad de los massienos. Y en el fondo del golfo se levantan las altas murallas de la ciudad de Massia...
No hay pruebas definitivas de que el texto se refiera a la ciudad de Cartagena, aunque por el contexto y el resto de descripciones de accidentes geográficos que anteceden, por ejemplo el de la toponimia, hacen referencia a cinco colinas, que bien podrían ser las de Cartagena (Molinete, Monte Sacro, San José, Despeñaperros y Concepción). También ha habido estudiosos que han ubicado Mastia en algún punto cercano a Mazarrón o en la antigua ciudad de Carteia (Cádiz), situada al fondo de la bahía de Algeciras.
La presencia de los tartesios en España equivale a un tiempo de esplendor cultural y comercial. Mastia exportaba su esparto, el garum, sus salazones y sus minerales (hierro, plomo, plata, cinc y cobre) a diferentes pueblos como los celtíberos, los cartagineses y los romanos.
La agricultura (en la que se producían alcachofas, cebollas, frutales, lino, olivos y vides) y la ganadería (con la elaboración de lana y miel) fueron también importantes en la vida mastiena.
En cuanto a la flora, hubo también vegetación autóctona. Destacan la pita, utilizada para la elaboración de tejidos, el pino, con el que se obtenía la resina para el calafateo de las naves y el esparto, útil para la realización de las cuerdas de los barcos.
Finalmente, cabe destacar que, en esta época, Cartagena, gobernada por el Consejo de Ancianos, también fue amurallada y se encontraba estructurada excelentemente, calles bien alineadas, con conducciones de aguas, puertas de acceso, santuarios situados en los puntos más altos (se cree que dos, el de la longevidad y el de la salud) y necrópolis cercanas. El puerto empezó a ser destacado en el Mediterráneo, con la llegada de fenicios, griegos y egipcios. Además, este contaba con veloces embarcaciones pesqueras, en los que destacaban los mascarones de proa (cabezas de caballo).