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.