Shortly thereafter, in 1532, in the bottomlands of the Colorado River of Texas, where several bands were harvesting walnuts, Cabeza de Vaca stumbled joyously across Castillo, Dorantes, and the vigorous black Estéban. The trio were also ready to strike for Mexico if they could escape from their masters, but they warned against fierce tribes to the southwest. They should try a route farther north.

After two years of interruption and frustrations they made the break. The incredible journey, broken by long stays at various Indian camps, lasted two years. At times they traveled alone. More often they were accompanied by Indians. After they had chanced to pray over an ailing man, who thereupon leaped up and declared himself cured, they became revered as supernatural medicinemen, children of the sun. Their marches, often scouted out for them by Estéban, who also served as interpreter—he learned six languages during those arduous years—became triumphal processions. Sometimes, says Cabeza de Vaca, as many as 4,000 Indians would accompany them from one village to the next, a figure that, as Bernard DeVoto has pointed out, should be taken as a way of saying “quite a few.” Those who escorted them would often loot the first village they reached, whereupon its inhabitants, moving on with the quartet to another village, would recoup their losses by plundering it.

What route did they follow? No one knows. Cabeza de Vaca’s descriptions of Indian customs, rivers, mountains, vegetation, and so on have led some students to suggest that the wanderers may have gone as far north as southern New Mexico and Arizona. Others think they traveled out of west Texas into Chihuahua. But whatever the way, it eventually merged with one of the trade trails that ran between the Pueblo Indian towns of the Southwest and those in the heavily populated, southward trending valleys of Sonora. They reached the Sonora area in the spring of 1536.

What had they seen along the way? Not much, according to a report that the survivors sent to the audiencia in Hispaniola in 1537. Just buffalo robes that had originated in the country of the plains Indians and beautifully woven cotton mantas that their native hosts had obtained by trade with Indians somewhere in the north (probably the Pueblos of the Rio Grande). Bits of coral and turquoise. And miles and miles of desolation, thinly populated by primitive tribes. Writing a memoir of the trip six years later, Cabeza de Vaca improved only slightly on the tales. In Sonora, he related, he was given five emeralds shaped like arrowheads; the donors said the “jewels” had been purchased in the north with parrot feathers and plumes. Sadly, he lost the five artifacts before anyone else saw them. He also told of handling a small bell made of copper and of hearing stories about large cities filled with big houses and surrounded by boundless fields of maize.

Such reports were too vague and understated to create much popular excitement—at first. But as Antonio de Mendoza, New Spain’s first and recently arrived Viceroy, realized, the calm might not last. For a similar story told a few years earlier to the infamous Nuño de Guzmán by an Indian slave named Tejo had stirred up a violent reaction.

At the time Guzmán had been governor of Pánuco on Mexico’s northeast coast and was making a fortune selling slaves to plantations throughout the West Indies. But that wasn’t enough, and his ears pricked up when he listened to Tejo telling about a trip with his father to seven marvelous cities far to the northwest—cities whose streets were lined with the shops of goldsmiths and silversmiths.

The story may well have had an element of truth in it. If a trader kept traveling northwest from Pánuco—and some of Mexico’s early Indian traders were far-ranging—he would eventually reach the impressive pueblo towns of today’s New Mexico. Where the notion of goldsmiths came from is something else, but Guzman believed it because he wanted to.

Instead of taking a direct line to his goal, he put together a strong force, fought his way across the mountains to the west coast, and hewed out, as a base of operations for a thrust along the trade trails leading north, the all-but-independent province of Nueva Galicia. (It embraced the better part of the present-day Mexican states of Nayarit and Sinaloa.) Illness and then his arrest for his slave-dealings put a stop to the northern plans, but the appearance of the Vaca party out of the wilderness might, Mendoza feared, lead the great Cortés to appropriate the idea for himself.

Cortés was ripe for trouble. Because of his insubordination to Diego Velásquez of Cuba, the king had refused to name him Viceroy of New Spain, but then had tried to compensate for the injustice, as Cortés considered it, by naming him the Marquís of the Valley of Oaxaca and giving him the right to explore the South Seas (south of Asia) for new principalities. On their quests some of his ship captains stirred Guzmán’s jealousy by sailing north along the coast of Nueva Galicia. When Guzmán seized one of those ships in the port of Chiametla, the Marquís rushed up with a small army and took it back. He then used that ship to cross what he called the Sea of Cortés (today’s Gulf of California) and claim possession, in the name of the king, of pearl fisheries his mariners had discovered at La Paz in what we call Baja California. The fisheries were not proving lucrative, however, and the least sign that something better existed farther north might tempt him to push on.

It behooved Mendoza, as the king’s representative, to move first, before New Spain’s legitimate northward expansion was halted by one of these semi-autonomous conquistadores. Dutifully reporting each of his moves to Charles V—caution was part of his nature—he asked, in turn, Castillo, Dorantes, and Cabeza de Vaca to lead a small exploring party into the north and learn what was really there. Not surprisingly, in view of their experiences, each refused.