"It would have been absolutely amazing to have seen this place back then," says Stuart Bedford, an archaeologist from the Australian National University and co-leader, along with Matthew Spriggs, of the excavation on Éfaté. "These islands were far richer in biodiversity in those days than they are today." By way of illustration, he picks up a trochus shell the size of a dinner plate that was exposed in a test trench only that morning. "The reefs then were covered with thousands of these, each one a meal in itself. The seas were teeming with fish, and huge flightless birds could be found in the rain forest, virtually tame since they had never seen a human being. The Lapita would have thought they'd stumbled onto paradise."

As indeed it was. But theirs is a story of paradise found and lost, for although the Lapita were a Neolithic people, they had a modern capacity for overexploiting natural resources. Within a short span of time—a couple of generations, no more—those huge trochus shells vanished from the archaeological record. The plump flightless birds followed suit, as did a species of terrestrial crocodile. In all, it's estimated that more than a thousand species became extinct across the breadth of the Pacific islands after humans appeared on the scene.

Still, more than a millennium would pass before the Lapita's descendants, a people we now call the Polynesians, struck out in search of new territory. The pioneers who launched this second age of discovery some 1,200 or more years ago faced even greater challenges than their Lapita ancestors, for now they were sailing out beyond the island-stippled waters of Melanesia and western Polynesia and into the central Pacific, where distances are reckoned in thousands of miles, and tiny motes of islands are few and far between.

How difficult would it have been to find terra firma in all that watery wilderness? Consider this: When Magellan's fleet traversed the Pacific in 1520-21, sailing blind across an unknown sea, they went nearly four months without setting foot on land. (They missed the Society Islands, the Tuamotus, and the Marquesas, among other archipelagoes.) Many of the hapless sailors died of thirst, malnutrition, scurvy, and other diseases before the fleet reached the Philippines.

The early Polynesians found nearly everything there was to find, although it took them centuries to do so. Their feats of exploration are remembered and celebrated today at cultural festivals across the Pacific.