Born in Zaragoza, Olid grew up in the household of the 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 caused the loss of Olid's anchors, and he returned to Cuba. On January 10, 1519, Olid sailed with Hernán Cortés' fleet, as his quartermaster, and took an active part in the conquest of Mexico.:39,200,278,286,293,297,299,309 He fought at the Battle of Otumba on 14 July 1520,:304 and also took part in the campaign against the Purépechas.
During the Siege of Tenochtitlan, Cristobal was one of Cortes' key captains, playing a critical role in the capture of Xochimilco.:315,317,319,333,339,340-343 Cristobal was the Texcoco camp commander during the trial of Antonio de Villafana, for his plot to assassinate Cortes.:351 Cristobal commanded one of four forces under Cortes, and acted as quartermaster.:356,358,360-363,383 Olid helped save Cortes at one point, when he was seized by the Mexicans in one of the causeway battles.:380
Cortes sent Olid to Michoacan, after he had married a Portuguese lady.:413
In 1523, Cortés made Olid the leader of an expedition to conquer Honduras, but while resupplying in Havana, Olid (at a suggestion by Velázquez) declared his independence from Spain and set out to conquer Honduras for himself. Landing east of Puerto Caballos, he founded the settlement of Triunfo de la Cruz. Many of Olid's supporters moved to Naco, where there was good agricultural land and gold. When Cortés learnt of Olid's rebellion, he sent Francisco de Las Casas against Olid with two warships. Despite the fact that both these ships were destroyed in a storm and many of his soldiers defected to Olid, Las Casas defeated Olid in battle and captured him.
Accounts of how Olid died vary; Bernal Díaz del Castillo asserts in his Verdadera Historia de la Conquista de Nueva España that Las Casas had him beheaded at Naco, while Antonio de Herrera y Tordesillas wrote that Olid's own soldiers rose up against and then murdered him.