Rodrigo de Bastidas was the first spaniard known to come close to the shores of Cartagena de Indias. He was a notary in Sevilla and had accompanied Christopher Columbus in one of his trips to America.
When he passed by the bay by mistake, he baptized it Golfo de Barú. In 1503 Queen Elizabeth The Catholic, would issue a Royal Provision where the name of "Bahía de Cartagena" would replace the original Rodrigo de Bastidas had given. It is said this name was suggested by the cosmographer Juan de la Cosa who was on the discovery expedition with Bastidas and was advisor to the Queen.
The similarity with the Bay of Cartagena de Levante in Spain was what inspired De La Cosa and the Queen.