In February 1517, Cordoba sailed from Cuba to the Yucatan Peninsula of Mexico with 3 ships and 110 soldiers; he was the first European to travel to this area, and the first to see the Mayan people. Cordoba had been sent to Mexico by Diego Velazquez, the governor of Cuba, to look for treasures to plunder. First Juan de Grijalva and then Hernan Cortes continued the Spanish exploration/conquest of Mexico.

In 1524, the Governor of Darien (now part of Panama), Pedro Arias de Ávila (also called Pedrarias Dávila), sent Hernandez de Cordoba to Nicaragua (Francisco de Soto accompanied him on this trip) to claim the land (and usurp the land claims of Gil González de Ávila ). On this trip, Cordoba founded the first permanent Spanish settlements in the area, including Granada (on Lake Nicaragua) and Leon (east of Lake Managua). After trying to claim Nicaragua for himself, Cordoba was killed by Pedro Arias de Ávila.