On a warm April morning, on a rising tide, the greatest survival epic in American history began just a few miles from Sarasota. This was nearly 500 years ago, in 1528, and a small fleet of Spanish ships was working its way along the low, green coast of Florida, looking for the opening to the great bay that they knew was in the vicinity. On board were some 400 men and women, mostly Spaniards, but also assorted free and enslaved Africans and Caribbean Indians and even a Mexican prince from Montezuma’s recently fallen empire.

They were all under the command of a red-haired, one-eyed, monomaniacal conquistador named Panfilo de Narvaez, whose goal was both simple and audacious. He had a license from the King of Spain to conquer the Gulf coast of North America and give the Indians the choice of becoming either Christians or slaves. “We came to serve God,” as one of his contemporaries put it, “but also to get rich.”

In the end, however, nobody in Narvaez’s army got rich. Instead, after an adventure that was one part Heart of Darkness, one part Moby Dick and one part Lewis and Clark, only four of the 400 aboard those Spanish ships would manage to cross America—becoming the first Europeans to travel the continent—and get out alive.

Narvaez wasn’t the first European to try to conquer “La Florida,” as the Spanish called the region. That honor goes to Juan Ponce de Leon, the official “discoverer” of the peninsula, who made a fortune conquering Puerto Rico and came north in 1513, hoping to repeat his success and maybe find the fountain of youth. He arrived in the vicinity of Charlotte Harbor, where the first Indian he met greeted him in perfect Spanish. To Americans raised on the persistent myth of the dusky savage and the trackless wilderness, the idea that the first European to officially set foot in what would become the United States was met on the shore by a native who spoke a Romance language seems absurd. Ponce de Leon, on the other hand, was only mildly surprised, figuring that the multilingual Indian was a refugee from the Spanish gold mines in Cuba or some other already conquered island.

Whoever he was, the Indian knew enough about bearded men in metal hats to advise the local Calusa Indians that they had better waste no time in attacking the Spanish ships, and after two days of skirmishing, Ponce de Leon decided Florida wasn’t worth the trouble and pulled up his anchors and left. He returned in 1521, after the discovery of gold in Mexico made him think the peninsula might be worth a second look, but stayed only long enough to get shot in the backside with an arrow. It didn’t kill him immediately, but festered, ultimately causing his death after he and his army had fled Florida once again.

Panfilo de Narvaez and Ponce de Leon may have been friends: Both were old-Indies hands who had been around the Caribbean from the days of Columbus’ second voyage. But Narvaez probably wasn’t overly saddened by Ponce de Leon’s death, as it meant that the Florida territory was back in play, waiting for the King of Spain to assign it to another would-be conqueror. Even though Narvaez had already made a fortune of his own as the No. 2 conquistador in both Jamaica and Cuba, at roughly 50 years of age he was tired of always being the bridesmaid and wanted a command of his own. Making matters worse, he was supposed to have helped lead the conquest of Mexico, but at the last minute Cortes stole that golden opportunity out from under him. So Narvaez followed the King around Spain for months, hounding him for Ponce de Leon’s old contract and for the adjacent lands north of Mexico as well. Finally, in December of 1526, he got his wish: a royal contract to conquer a vast swath of the New World that stretched “from one sea to the other.” All he had to do was raise an army, buy a fleet of ships, and go make the continent his own.

It was this fleet that on Good Friday of 1528 cruised the Gulf coast of Florida, looking for an opening. Inexplicably, the fleet failed to find the main entrance to Tampa Bay, and finally Narvaez ordered the ships into one of the lesser bays in the vicinity—perhaps Boca Ciega Bay, or even Sarasota Bay. The crossing from Cuba had taken weeks longer than expected because of storms at sea, and provisions on board were running dangerously low. The horses, which were critical to the expedition’s success on land, were hanging in slings in the hold below deck, and, in those miserable conditions, were dying at a rate of one per day.

It wasn’t where Narvaez had hoped to begin his glorious conquest, but given the circumstances, the medium-sized fishing village at the back of the shallow bay would have to do. He knew from experience that improvisation was as important as planning in adventures such as these, and he ordered his hungry army to disembark and take the town, which the Indians had wisely abandoned. He was also certain that no great achievements came without great risks, and after a day or two of rest, he made a fateful decision. He announced that he would march the army inland while the ships continued to look for Tampa Bay.

The royal treasurer for the expedition, a somewhat prim and inexperienced courtier, was horrified by the plan. Alvar Nunez Cabeza de Vaca never really got along with Narvaez, and he argued now that if they didn’t leave the ships in some known location before they set off inland they would never see them again.

But Narvaez would have none of it. He may even have wanted to separate his army from the ships precisely to eliminate the temptation to run back to port when things got tough. He knew that his old nemesis, Cortes, had destroyed his own fleet for that very reason before marching inland to Mexico City. So into the flickering green jungle the army marched—a long, colorfully dressed line of pike men, horsemen, dog handlers, crossbowmen and slaves. Behind them, now on a falling tide, the ships with their crews and all the women dropped back through the opening into the Gulf of Mexico.

Unfortunately for everyone involved, Cabeza de Vaca was right. They never did see the ships again. Once in a while, as the hungry army, dressed in heavy European clothes and armor, worked its way through insect-infested, sweltering swamps and forests up the Florida peninsula, Narvaez sent a scouting party back out to the coast. But every time it was the same: no bay, no harbor, no town, no ships, no hope. Just endless sawgrass and the flat blue sea.

Meanwhile, none of the Indian villages they came across inland raised enough food to feed the army for more than a day or two. In these towns violence erupted occasionally, more out of frustration than necessity. In one place, Narvaez apparently sicced his deadly war dogs on a local leader’s mother; in another, he burned a burial temple because the priests in his company were certain it represented some kind of deviltry.

Mostly, though, the would-be conquerors and their slaves trudged through the flickering light on footpaths worn into the soggy ground by people they never saw but who were presumably keeping an eye on them. Startled deer sometimes ran past, but the crossbowmen were not skilled enough to hit any, so they survived primarily on the hearts of palms. The only good news was that the few Indians they managed to capture in central Florida seemed to agree that there was a great civilization, loaded with corn and gold, somewhere far to the north. They had no translators, but whenever a Spaniard held a piece of gold and some corn up to the captives’ faces, the Indians pointed north and mentioned a place called Apalachee or Palachen or some such thing. Cabeza de Vaca, who was one of the four who ultimately survived, and who wrote the most important account of the journey, said that during those weeks Apalachee “was what they most wanted in the world.”

The Apalachee were, in fact, a very powerful and well-organized people. Their main city was at the current location of Tallahassee, and their territory included much of the Florida Panhandle. They were the southernmost example of what archaeologists today call “Mississippian” culture: a broad collection of hundreds of different native nations that built great mound cities and raised prodigious amounts of corn in the river valleys of the Midwest. The Apalachee were a sports-mad people and, by all Spanish accounts, much larger and healthier than the average European. Fantastic archers, they were not at all amused when Narvaez and his starving army took over a medium-sized border town near the Aucilla River and held its mayor hostage. Twice they attacked in great numbers and succeeded in burning down the huts within the stockade fence. But they were unable to drive the Spaniards out, and so they changed their strategy to something between a guerrilla insurgency and a siege.

Archers harassed Narvaez’s people any time they were in small groups or away from their stronghold in the village center. “The Indians made war on us continually,” remembered a survivor, “wounding the people and the horses when we were at the places where we went to get water, and doing this from the lagoons and so safely that we could do them no harm.” All of this might have been tolerable had there been any sign of gold or other precious goods to make it worth putting up a fight. But there was none.

Morale, already low, collapsed. They had marched across Florida to Apalachee on the premise that there was gold to be had and civilization to spread. Now here they were, after only a few months, hunkered down in a burned-out town in the middle of nowhere, getting shot at by naked giants every time they turned their backs for a moment or two. The Apalachee “were beginning to wound their people,” the survivors later recalled. It was a quagmire, and everyone smelled disaster. After three weeks of this, Narvaez, now racked with chills and fevers from a strange malady that was sweeping through the ranks, decided to retreat to the sea.

As bad as things were up to that point, the march to the Gulf of Mexico was worse. Their captured Apalachee “guides” led them through one swamp after another. When they were chest deep in the middle of God knows where, in the midst of a tangle of hurricane-downed trees, the Apalachee attacked from both sides. Swords, lances, horses, artillery—the prized, high-tech weapons of the most powerful empire on earth at the time—were all but useless in the situation. Arrows flew in and ripped through any exposed flesh, but whenever a conquistador turned to see who had fired the missile, there was no one in sight. After days of this misery, Narvaez’s great army of conquest limped feverishly into an Indian village called Aute, in what is now St. Marks National Wildlife Refuge, in the corner of the Florida Panhandle.

It felt like the end of the road, and it was. The horsemen talked mutinously among themselves of riding off and leaving the others to their fate. But where would they go? No one knew where the ships were. Meanwhile, the guerilla attacks resumed, and the mysterious disease kept spreading among the men. “We held it to be certain,” remembered Cabeza de Vaca, “that nothing could follow but death.”

Their only hope lay in a plan concocted by one of the lesser members of the expedition. His name is forgotten, but in the darkest hour he approached Narvaez and told him he thought it might be possible to build a makeshift forge and melt down their war materiel to make hardware for boats, in which they might sail along the coast to the Spanish outposts in Mexico. No one was sure how far west that really was, but it was at least a plan, and it invigorated the troops, who set to work immediately. Teams twisted palmetto into ropes, felled trees, made charcoal for the forge, or raided nearby Indian villages for corn. Every three days a horse was butchered, and its hide hung out to dry in the hope that it could be used later for a water bottle. By the end of September, five makeshift boats were finished; and the 242 members of the army who were still alive piled aboard, shoved off and headed toward the sunset.

They stayed as close to shore as possible, but it wasn’t what you’d call a pleasure cruise. The water bottles failed almost immediately, and five men died of dehydration. Others decided they’d had enough and “went native,” choosing to go off with some of the Indians. In one village where they spent the night, their hosts tried to brain them with rocks as they slept. Progress was steady, however, until they rounded a corner to find the mile-wide mouth of the Mississippi, draining the vast continent they had once hoped to conquer. It caught up their measly boats and spit them far out to sea like bits of bad food. A wicked north wind picked up and pushed them out some more, until the coast of America disappeared altogether.

During the night the boats became separated, in part because Narvaez had announced that from henceforth, it was every man for himself. One came ashore at the bottom of Texas on Pedro or Mustang Island, where the local Indians immediately killed its passengers as they crawled up the beach. The other four boats, however, came ashore relatively safely in the vicinity of Galveston, Texas, and the adjacent Matagorda peninsula.

At first the local Karankawa Indians, hunter-gatherers who never had much in the way of a surplus, tried their best to aid the various groups of strangers who washed ashore. But it was November, winter was approaching, and many of the castaways died of exposure and disease. Relations with the Indians soured considerably after it was discovered that some of the Spaniards living in a camp on the beach had resorted to cannibalizing the remains of their former comrades. They soured further when a mysterious disease the Spanish were suffering from spread to the locals. Narvaez disappeared one night while sleeping alone in the last workable boat, and his designated deputy was murdered by a disgruntled rival. By mid-winter only a hundred were left in the army; by spring, there were only a few dozen, spread out in small groups along the Texas coast from Galveston to Matagorda Bay.

Among those living on Galveston Island were about a dozen who felt healthy enough by June of 1529 to continue making their way west on foot. They didn’t get far, however, before they were enslaved by some rough tribes who migrated between the pecan groves of the Guadaloupe River valley and the prickly pear forests near the Mexican border. Years went by in captivity—1529, 1530, 1531—and their numbers dwindled until only three were left, two Spaniards named Castillo and Dorantes, and a black Arabic-speaking Moroccan named Esteban. Twice, the three of them tried to escape while their captors were harvesting prickly pear fruits, but twice their plans were foiled.

Meanwhile, Cabeza de Vaca, whom they had left for dead in Galveston, managed to recover and was making a good living as a peddler. He traveled from tribe to tribe over a broad swath of Texas and perhaps Arkansas, trading seashells, flints, face paint and the like. It wasn’t a bad life, spending his summers on the road and winters in a snug hut with his friends the Charruco. But by 1532 he, too, was ready to make one last effort to get home and traveled down the beach, where he happily reunited with the other three survivors—though like them, he was quickly enslaved.

These last four members of Narvaez’s grand army of conquest made their escape from the prickly pear forests one night under a full moon. They were aided in their getaway by a friendly tribe called the Avavares, wanderers who specialized in selling wood for making bows to Indians who lived in treeless areas. But they didn’t remain with the Avavares long, as they were now determined to jump quickly from tribe to tribe until they got to the Spanish outposts in Mexico. Over the course of the next year they lived with dozens, perhaps hundreds, of different tribes, and their story slowly veered from the merely horrifying into the truly bizarre.

How it all began is a bit murky. Cabeza de Vaca mentions being pulled aside by a local shaman and told that even the rocks have magic, so he, too, must have power, and that he’d better start using it to heal the sick or he wouldn’t get any more food. The message was clear, and Cabeza de Vaca mumbled a few Latin prayers he knew from his youth. He made some motions of the cross over the sick man, mixed in a bit of shamanism he’d seen along the way—some shaking and blowing—and, lo and behold, the patient was cured.

Word of the healing spread like wildfire among the tribes living in the vicinity of the Rio Grande. People came from all around to be touched and healed by the wandering holy men, holding out infants, showering them with gifts of food and other items. In one town, a man was apparently raised from the dead; in another, the blind regained their vision.

Later, Cabeza de Vaca humbly credited God for the miracles that he and his companions claimed to have performed, but at the time they threw themselves wholeheartedly into their new role of shamans, which turned them from hapless captives into protected deities.

The four traveled now with a huge entourage of followers, who were in the habit of raiding the food stores of each new village they entered. This traveling medicine show was a high stakes game, and more than once the situation threatened to get out of hand. Still, it got them all the way to the Pacific Ocean and then down to the Spanish frontier, where they ran into a band of Spanish slave hunters in search of fresh labor for the mines. Cabeza de Vaca tried to protect his congregation from being rounded up, but it was no use. After eight years of wandering, the four travelers were back in “civilization,” and many of their followers were promptly rounded up and put in chains.

For their own part, the four survivors were greeted in Mexico City as heroes of the first order, men back from the dead. There were fancy dinners with Cortes and the King’s new viceroy, Mendoza, who wanted to hire them as guides for a new expedition north. Cabeza de Vaca declined the offer, though not because he wanted nothing more to do with the great unknown territory that would one day become the United States. Quite the opposite: Like his old boss Narvaez, Cabeza de Vaca now wanted the contract to conquer that same land for himself, and he hurried across the Atlantic to petition the King.

But he was too late. With everyone in the Narvaez expedition long since assumed to be dead, the contract for La Florida had been awarded to a man named Hernando de Soto. De Soto, in fact, was already in the process of raising an army and collecting a fleet, preparing to sail for Tampa Bay. That, however, is another story altogether.

In addition to Brutal Journey, Paul Schneider has written two other non-fiction books, The Adirondacks and The Enduring Shore, and he contributes to a wide variety of national publications, including Oprah, Esquire and The New York Times. He lives with his wife and son in Bradenton.