Miasto zostało założone w 1532 roku przez Pedra de Heredię.

Od 24 kwietnia 1534 siedziba rzymskokatolickiego biskupa (od 20 czerwca 1900 arcybiskupa).

W XVI stuleciu port ten posiadał bardzo skromne fortyfikacje, mimo swojego znaczenia: był jednym z portów w hiszpańskiej Ameryce, do którego zawijała flota hiszpańska wywożąca z kontynentu do metropolii złoto, srebro i wszelkie inne dobra materialne. Dlatego nie sprawiło trudu sir Johnowi Hawkinsowi w latach 1568–1569 skłonienie mieszkańców Cartageny (podobnie jak Santa Marty) do handlu z jego flotą złożoną z 6 okrętów, mimo że łamało to hiszpański monopol: ostrzelanie słabo ufortyfikowanego miasta okazało się wystarczającym argumentem. W lutym 1586 roku miasto zostało zdobyte przez potężną flotę Drake’a. Mieszkańcy musieli słono się okupić, aby miasto nie zostało zrównane z ziemią. Angielskie ataki na hiszpańskie posiadłości w drugiej połowie XVI wieku sprawiły, że król Filip II zdecydował się na znaczną rozbudowę systemu fortów w swych amerykańskich posiadłościach. Odpowiedzialnymi za to uczynił: generała Juana de Tejadę oraz włoskiego inżyniera wojskowego Bautistę Antonellego. Tejada i Antonelli udali się w latach 1586–1587 do Ameryki aby zbadać stan fortyfikacji i opracować plan rozbudowy. Został on zatwierdzony przez króla w listopadzie 1588 roku. Ponieważ oczywiste było, że nie da się silnie ufortyfikować wszystkich portów i osiedli w hiszpańskiej Ameryce, wybrano 10 najważniejszych, leżących na trasie „złotej floty”, w tym Cartagenę.

Od 1602 roku zaczęto rozbudowę istniejącego od lat 60. XVI wieku fortu San Matias, strzegącego wejścia do portu. W 1603 roku po drugiej stronie kanału, którym wpływało się do portu, wzniesiono baterię Fort Santangel, aby zapewnić ogień krzyżowy (ukończono go w 1631 roku). Od 1614 roku rozpoczęło się otaczanie murami miasta. Do lat 40. wzniesiono porządne mury z bastionami choć miasto nadal nie miało twierdzy. W pierwszej połowie XVII wieku wznoszono kolejne forty w okolicy, nad zatoką i portem: Santa Cruz, San Juan de Manzanillo, San Luis de Bocachica i inne. Na północny wschód od miasta znajdowało się małe wzgórze San Lazaro, które w razie oblężenia mogło stać się wymarzonym miejscem dla wroga aby ostrzeliwać miasto z wysokości. Postanowiono zabezpieczyć ten punkt i w 1647 roku ruszyły tam prace nad fortem San Felipe de Barajas. W latach 70. XVII wieku zagrożenie ze strony okrętów angielskich (m.in. zajęcie miasta Panama) skłoniło Hiszpanów do ulokowania w Cartagenie na stałe pewnych sił morskich.

W roku 1697 miasto zostało zajęte przez siły francuskie pod wodzą barona de Pointis wsparte przez korsarzy. Znacznie został wtedy zniszczony Fort Bocachica (odbudowany i wzmocniony w latach 1719–1725). Sukces Francuzów zaskoczył Hiszpanów i ukazał im konieczność dalszych prac fortyfikacyjnych w rejonie Cartageny. Nadzór nad nimi został powierzony inżynierowi nazwiskiem Juan de Herrera y Sotomayor. W latach 1714–1725 wniósł on nowy fort, San Jose, oprócz tego zbudowano trzy małe baterie na półwyspie Teirrabomba.

Rozbudowane i ulepszone fortyfikacje Cartageny i jej portu miały okazję zostać wypróbowane już w 1741 roku, gdy pod wodzą admirała Edwarda Vernona, dowodzącego flotą 180 jednostek w tym 36 okrętów wojennych miał miejsce atak Anglików na Cartagenę. Zaciekłemu oporowi Hiszpanów (wzmocnionych przybyciem 2300 żołnierzy z metropolii w latach 1739–1740) sprzyjały nie tylko potężne fortyfikacje, ale i gorączka zbierająca śmiertelne żniwo wśród szeregów przeciwnika. Po krótkim czasie Vernon odpłynął. Mimo wspaniałego zwycięstwa Hiszpanie nie spoczęli na laurach i ulepszanie fortyfikacji trwało. W latach 50. XVIII stulecia rozbudowano fortyfikacje w rejonie Bocachica, powstały tam trzy nowe forty.