Menéndez traveled to southwest Florida, looking for his son. There he made contact with the Calusa tribe, an advanced maritime people, at what is now known as Charlotte harbor. He negotiated an initial peace with their leader, Carlos, which was solidified by Menéndez's marriage to Carlos's sister, who took the baptismal name Doña Antonia. The peace was uneasy, and Menéndez's use of his new wife as a hostage in negotiations with her people, as well as his negotiating with the Calusas' enemies, the Tocobagas, helped cause the decline of relations to all out war, which continued intermittently into the next century. Menéndez was unsuccessful in locating his son Juan.