A Spanish-led expedition started in June 1527 when conquistador Pánfilo de Narváez left Spain with five ships containing Esteban and about 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. Natváez bought anoher ship on Hispaniola. After spending the summer there, Narvåez took his six ships to Cuba. There a hurricane sank two of his ships, with 60 men, 20 horses, and a quantity of supplies lost. The remaining ships spent the next few months along Cuba's southern shore in a protected anchorage.
In the spring the four ships and a shallow-draft brigantine set sail, battling storms all around western Cuba and into the Gulf of Mexico, landing about fifteen miles north of present-day Tampa Bay and St. Petersburg in April 1528. One ship was lost along the "wild coast," leaving Narváez with three ships and the brigantine. 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 300 Europeans plus scores of slaves and servants. Indians tired of the expedition's warlike behavior and depredations, tricked Narváez into going to northern Florida in search of gold. Instead of gold, however, the expedition found only 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 Esteban and about eighty of the Europeans were still alive. By the spring of 1529, Esteban and three Spaniards were survivors. (A fifth man is rarely mentioned. The story of Lope de Oviedo is told in the blog entry titled "The man left behind.") Different bands of Karankawa Indians then enslaved the five survivors for more than five years along coastal Texas.
Esteban and three Spaniards -- Cabeza de Vaca, Castillo, and Esteban's slaveowner Dorantes -- escaped from the Karankawas in the fall of 1534. Other tribes treated them as faith-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 on foot most of the way for 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.