The strange tale of Álvar Núñez Cabeza de Vaca defies belief. As one of Spain's conquistadors, he was set to pursue a path of plunder and conquest in the New World. Fate, however, had other (more interesting) ideas.
Cabeza de Vaca (the name literally means "Head of the Cow"more on this in the examples section) came from proud Spanish military stock. Upon going to the New World, he joined up with the Narvaez Expedition, which had been assigned to explore and create towns along the present day US Gulf Coast. De Vaca acted as the group's treasurer, making sure that all the soldiers received recompense.
The expedition's first stop was in what's now called Tampa Bay, and things immediately started to turn pear-shaped. They worked their way north, alternately trading with and fighting the natives, and reached Apalachee Bay stinking, starving, and half-delirious. Much of this was Narvaez's fault, as he decided to split up the land expedition from the fleet in hopes of covering more ground. Had they stuck with the ships (as de Vaca had suggested), they might not have gotten lost (the ships were comfortably back in Havana at this point). Of the 600 men who started in the expedition, only 242 still lived by the time they reached Apalachee Bay.
They thought they were close to Spanish Mexico, not realizing that they were 1500 miles away from it. Separated from their ships, they made five crude boats. To get nails and other supplies, they melted down all the metal they had, and ate their horses for food. With nothing more than this meager fleet, they set across the storm-tossed Gulf of Mexico.
Only two of the ships, with about 40 men between them, survived the journey. Narvaez's boat was lost in a storm. De Vaca and company landed on Galveston Island, which they cheerily dubbed the Isle of Doom. A strong tide swept away their damaged boats, leaving them stranded and at the mercies of the local natives. Starvation, disease, and exhaustion further diminished their numbers until only four remained.
Naked, hungry, and hopelessly isolated, de Vaca did what he did best: he survived. Forced into a vulnerable position, he made himself useful to the natives as a trader. He walked from camp to camp, going hundreds of miles across the harsh deserts of northern Mexico, going as far as the Gulf of California. Learning the local languages, he became adept at navigating the difficult geological and political terrain.
Though an able traveler, he still had more than his share of misfortune. He spent several years as a slave for a tribe near the Gulf of Mexico. He continued traveling after his escape, gaining a reputation as a local healer. De Vaca didn't have any medical background (though given the era, having one probably wouldn't help anyway), but he observed the local remedies and combined them with religious theater (laying on hands, the sign of the Cross, etc), and succeeded enough times to earn respect.
He even got an entourage that followed him on his journeys. They often helped themselves to the food of their hosts. Thus deprived, the former hosts would follow de Vaca to the next tribe, and so forth. De Vaca developed a great deal of respect for the people around him. While his peers enjoyed the power given to them by guns and steel, de Vaca had no choice but to adapt and to learn.
He finally returned to the Mexico City in 1537, ten years after he started on the expedition. Sailing back to Spain, he wrote about his journeys in a document called the Account. It's still published today, and is an excellent read.
However, the New World wasn't done with de Vaca. He returned for another expedition, this time into South America in hopes of re-establishing the town of Buenos Aires. He ended up going farther west to Asuncion, which is now the capital of Paraguay. Things went badly for de Vaca. He was infuriated at the cruel manner in which his compatriots treated the Native Americans, and tried to intervene on the natives' behalf. He eventually got arrested and sent back to Spain in 1544. Pardoned, he spent the rest of his life in poverty.
De Vaca was nearly unique in being a conquistador who had no choice but to approach the indigenous Americans as fellow humans (who generally held power over him).