Jon Erlandson shakes out what appears to be a miniature evergreen from a clear ziplock bag and holds it out for me to examine. As one of the world’s leading authorities on ancient seafaring, he has devoted much of his career to hunting down hard evidence of ancient human migrations, searching for something most archaeologists long thought a figment: Ice Age mariners. On this drizzly late-fall afternoon in a lab at the University of Oregon in Eugene, the 53-year-old Erlandson looks as pleased as the father of a newborn—and perhaps just as anxious —as he shows me one of his latest prize finds.

The little “tree” in my hand is a dart head fashioned from creamy-brown chert and bristling with tiny barbs designed to lodge in the flesh of marine prey. Erlandson recently collected dozens of these little stemmed points from San Miguel Island, a scrap of land 27 miles off the coast of California. Radiocarbon dating of marine shells and burned twigs at the site shows that humans first landed on San Miguel at least 12,000 years ago, and the dart head in my hand holds clues to the ancestry of those seafarers.

Archaeologists have recovered similar items scattered along the rim of the North Pacific, and some have even been found in coastal Peru and Chile. The oldest appeared 15,600 years ago in coastal Japan. To Erlandson, these miniature trees look like a trail left by mariners who voyaged along the stormy northern coasts of the Pacific Ocean from Japan to the Americas during the last Ice Age. “We haven’t published the evidence for this hypothesis yet, and I’m kind of nervous about it,” he says. “But we are getting very close.”

Until recently most researchers would have dismissed such talk of Ice Age mariners and coastal migrations. Nobody, after all, has ever unearthed an Ice Age boat or happened upon a single clear depiction of an Ice Age dugout or canoe. Nor have archaeologists found many coastal campsites dating back more than 15,000 years. So most scientists believed that Homo sapiens evolved as terrestrial hunters and gatherers and stubbornly remained so, trekking out of their African homeland by foot and spreading around the world by now-vanished land bridges. Only when the Ice Age ended 12,000 to 13,000 years ago and mammoths and other large prey vanished, archaeologists theorized, did humans systematically take up seashore living—eating shellfish, devising fishing gear, and venturing offshore in small boats.

But that picture, Erlandson and others say, is badly flawed, due to something researchers once rarely considered: the changes in sea level over time. Some 20,000 years ago, for example, ice sheets locked up much of the world’s water, lowering the oceans and laying bare vast coastal plains—attractive hunting grounds and harbors for maritime people. Today these plains lie beneath almost 400 feet of water, out of reach of all but a handful of underwater archaeologists. “So this shines a spotlight on a huge area of ignorance: what people were doing when sea level was lower than at present,” says Geoff Bailey, a coastal archaeologist at the University of York in England. “And that is especially problematic, given that sea level was low for most of prehistory.”

Concerned that evidence of human settlement and migration may be lost under the sea, researchers are finding new ways of tracking ancient mariners. By combining archaeological studies on remote islands with computer simulations of founding populations and detailed examinations of seafloor topography and ancient sea level, they are amassing crucial new data on voyages from northeast Asia to the Americas 15,000 years ago, from Japan to the remote island of Okinawa 30,000 years ago, and from Southeast Asia to Australia 50,000 years ago. New evidence even raises the possibility that our modern human ancestors may have journeyed by raft or simple boat out of Africa 60,000 to 70,000 years ago, crossing the mouth of the Red Sea. “If they could travel from Southeast Asia to Australia 50,000 years ago, the question now is, how much farther back in time could they have been doing it?” Bailey asks. “Why not the Red Sea?”

Our new understanding of climate and sea-level change sheds light on something that has long puzzled archaeologists: How did modern humans colonize the far reaches of the globe so quickly after their exodus from Africa? If Erlandson and his colleagues are right, it was a series of sea voyages and river crossings that brought our ancestors to alien lands, launching the greatest biological invasion of all time.