The expedition started in June 1527 when conquistador Pánfilo de Narváez left Spain with six ships containing Esteban and 600 European men and women, mostly Spaniards. The ships arrived at Hispaniola (the present island nations of Haiti and Dominican Republic) after sailing for two months across the Atlantic Ocean and into the Caribbean Sea. After spending the summer there, Narvåez took his ships to Cuba. There a hurricane sank two of his ships, with many men, horses, and a quantity of supplies lost. The remaining ships spent the next few months along Cuba's southern shore in protected anchorages.
In the spring the ships set out again, battling storms all around western Cuba and into the Gulf of Mexico, landing near present-day Tampa Bay and St. Petersburg in April 1528. Soon Narváez separated the men from his ships. In hopes of finding gold, Narváez marched into Florida's swamps and forests with Esteban and more than 300 Europeans. Indians tired of the expedition's warlike behavior and depredations, tricked Narváez into going to northern Florida in search of gold. Instead, the expedition found itself fighting warriors of the powerful Apalachee tribe.
After many deaths from battles and illnesses, the expeditionaries built hand-made boats to escape Florida by crossing the Gulf of Mexico. By the time the boats washed ashore after 44 or more days, only 80 Europeans and Esteban were still alive. By the spring of 1529, Esteban and three Spaniards were the survivors. Different bands of Karankawa Indians then enslaved them for more than five years along coastal Texas.
Esteban and the three Spaniards escaped from the Karankawas in the fall of 1534. Other tribes treated them as shaman healers as they made their way out of Texas and across northern Mexico. Esteban was their guide and intermediary with the tribes because of his language skills.
It would not be until March 1536 that the travelers would encounter Spanish slave-raiders. The four were escorted to Mexico City, arriving in July 1536, more than eight years after first landing in Florida.
Based on a measurement of straight-line distances, the four traveled almost entirely on foot 3,500 or more miles, if the distance is included that they walked in Florida, the 800 miles they sailed and rowed across the Gulf of Mexico, and their travels following rivers and detours for mountain passes in northern Mexico.