Olid was born in Zaragoza and grew up in the household of the colonial governor of Cuba, Diego Velázquez de Cuéllar. In 1518 Velázquez sent Olid to relieve Juan de Grijalva, but en route a hurricane destroyed Olid's ship and he returned to Cuba. On January 10, 1519, Olid sailed with Hernán Cortés' fleet, and took an active part in the conquest of Mexico. He fought at the Battle of Otumba on July 8, and also took part in the campaign against the Purépecha, who proved difficult foes due to their use of iron weapons, which the Aztecs lacked.