In 1536 werd begonnen met een eerste versterking op de heuvel San Lazaro, net buiten de oude ommuurde stad, om de toegang tot de baai waaraan Cartagena ligt beter te beschermen. Vanaf deze heuvel kun je een vijand vanuit alle richtingen zien naderen. In 1657 werd vervolgens een echt fort op deze plek gebouwd, door een Spaanse bouwmeester, Gaspar Mejia, op basis van een ontwerp van de Nederlander Ricardo Carr. Dit fort werd het Castillo San Felipe de Barajas genoemd, ter ere van de Spaanse koning Philips II.

In 1741 speelde het fort de hoofdrol in de Slag om Cartagena. De Engelse admiraal Vernon besloot Cartagena te veroveren als onderdeel van de Spaans-Engelse oorlog. Hij viel aan met 26.000 man, tegenover de magere 3.600 die de verdedigende Spaanse admiraal Blas de Lezo tot zijn beschikking had. De Engelsen veroverden vrij snel het kleine fort bij de ingang van de baai en besloten vervolgens het Castillo San Felipe de Barajas te belegeren.

Dank zij strategische fouten van de Engelsen, goede tactieken en enorme onverzettelijkheid van de Spanjaarden, en tropische ziektes opgelopen in de moerassige baai door de Engelsen, werd het fort niet veroverd. De Engelsen verlieten de baai met achterlating van zo’n 18.000 doden. Blas de Lezo stierf kort daarna zelf aan tyfus, maar kreeg wel een standbeeld voor het fort.

Na de belegering door de Engelsen is het fort opnieuw versterkt en meermaals uitgebreid. Uiteindelijk verdedigden 63 kanonnen het fort.