Uit opgravingen blijkt dat dit gebied al rond 7000 jaar v. Chr. bewoond werd. De Spaanse ontdekkingsreizigers hebben begin 16e eeuw meerdere pogingen gedaan om hier steden te stichten. De eerste succesvolle poging was die van Pedro de Heredia. Hij stichtte Cartagena op 1 juni 1533. De stad was lange tijd een belangrijke schakel tussen Spanje en Zuid-Amerika mede door de grote Baai van Cartagena de Indias, waar de schepen veilig en beschut voor anker konden gaan.

Tijdens de 16e eeuw en de 17e eeuw was Cartagena een van de belangrijkste havens van de Zilvervloot en daardoor een gewild doel voor boekaniers. Zo werd de stad in 1585 ingenomen en geplunderd door Francis Drake. Drake had het plan de stad bezet houden om zo de toevoer van zilver naar Spanje blijvend te frustreren. De Spanjaarden hadden dit voorzien en de schepen met de waardvolle lading al op reis naar huis gestuurd. De buit viel tegen en Drake had onvoldoende mannen om de bezetting vol te houden en vertrok. De Spanjaarden versterkten de stad om een herhaling te voorkomen.

In 1697 viel de Franse admiraal Jean du Casse de stad aan. Spanje en Frankrijk waren in Europa in oorlog en boekaniers zagen hun kans om hiervan te profiteren. De Vrede van Rijswijk (1697) bracht niet alleen vrede tussen beide landen, maar betekende ook een einde voor de boekaniers. In maart 1741 werd de stad aangevallen door troepen van de Engelse admiraal Edward Vernon, die naar Cartagena oprukte met een eskader van 186 schepen met 2000 kanonnen en een marinierskorps van ruim 6000 man. Die aanval werd afgeslagen vanwege de krachtige tegenstand die geboden werd door generaal Blas de Lezo, diens garnizoen en de bevolking van de stad. Vernon vluchtte hierop voor een naderend Spaans ontzettingsleger, geleid door kolonel-ingenieur Carlos Suillars de Desnaux.

Na Vernon begon een periode van grote bloei die tot 1808 duurde. Er kwamen veel immigranten en de bevolkingsgroei leidde tot forse bouwactiviteiten waarmee de economische en politieke macht van de stad toenam. De rijkdom leidde tot de bouw van grote huizen en bibliotheken en drukkerijen werden geopend. Dit kwam allemaal abrupt tot een einde in 1808. In Aranjuez, in de regio Madrid, kwam de bevolking in opstand tegen koning Karel IV met als uiteindelijk resultaat de Franse bezetting van Spanje.

Meer dan 275 jaar stond Cartagena onder Spaanse heerschappij, maar dit kwam op 11 november 1811 tot een einde met de onafhankelijkheidsverklaring. De Onafhankelijkheidsoorlog die hierop volgde leidde tot een dramatische achteruitgang van de stad. De Spaanse generaal Pablo Morillo belegerde de stad gedurende drie maanden waarbij de stadsbewoners leden onder honger en ziekten. De stad kwam weer in Spaanse handen op 6 december 1815. Na de Venezolaanse Onafhankelijkheidsoorlog werd in 1821 de laatste Spaanse gouverneur verslagen, maar na zijn vertrek lag de stad in puin.

Cartagena bleef belangrijk als havenplaats voor het onafhankelijke Colombia. Er werd geïnvesteerd in een spoorlijn tussen Cartagena en Calamar, een belangrijke binnenhaven, waarmee de goederenoverslag in de haven toenam. Met het geld dat verdiend werd in de haven en de internationale handel kwam de industrie in de regio tot opkomst.