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.