Seventy-seven thousand years ago, a craftsman sat in a cave in a limestone cliff overlooking the rocky coast of what is now the Indian Ocean. It was a beautiful spot, a workshop with a glorious natural picture window, cooled by a sea breeze in summer, warmed by a small fire in winter. The sandy cliff top above was covered with a white-flowering shrub that one distant day would be known as blombos and give this place the name Blombos Cave.

The man picked up a piece of reddish brown stone about three inches long that he—or she, no one knows—had polished. With a stone point, he etched a geometric design in the flat surface—simple crosshatchings framed by two parallel lines with a third line down the middle.

Today the stone offers no clue to its original purpose. It could have been a religious object, an ornament or just an ancient doodle. But to see it is to immediately recognize it as something only a person could have made. Carving the stone was a very human thing to do.

The scratchings on this piece of red ocher mudstone are the oldest known example of an intricate design made by a human being. The ability to create and communicate using such symbols, says Christopher Henshilwood, leader of the team that discovered the stone, is "an unambiguous marker" of modern humans, one of the characteristics that separate us from any other species, living or extinct.

Henshilwood, an archaeologist at Norway's University of Bergen and the University of the Witwatersrand, in South Africa, found the carving on land owned by his grandfather, near the southern tip of the African continent. Over the years, he had identified and excavated nine sites on the property, none more than 6,500 years old, and was not at first interested in this cliffside cave a few miles from the South African town of Still Bay. What he would find there, however, would change the way scientists think about the evolution of modern humans and the factors that triggered perhaps the most important event in human prehistory, when Homo sapiens left their African homeland to colonize the world.

This great migration brought our species to a position of world dominance that it has never relinquished and signaled the extinction of whatever competitors remained—Neanderthals in Europe and Asia, some scattered pockets of Homo erectus in the Far East and, if scholars ultimately decide they are in fact a separate species, some diminutive people from the Indonesian island of Flores (see "Were 'Hobbits' Human?"). When the migration was complete, Homo sapiens was the last—and only—man standing.

Even today researchers argue about what separates modern humans from other, extinct hominids. Generally speaking, moderns tend to be a slimmer, taller breed: "gracile," in scientific parlance, rather than "robust," like the heavy-boned Neanderthals, their contemporaries for perhaps 15,000 years in ice age Eurasia. The modern and Neanderthal brains were about the same size, but their skulls were shaped differently: the newcomers' skulls were flatter in back than the Neanderthals', and they had prominent jaws and a straight forehead without heavy brow ridges. Lighter bodies may have meant that modern humans needed less food, giving them a competitive advantage during hard times.

The moderns' behaviors were also different. Neanderthals made tools, but they worked with chunky flakes struck from large stones. Modern humans' stone tools and weapons usually featured elongated, standardized, finely crafted blades. Both species hunted and killed the same large mammals, including deer, horses, bison and wild cattle. But moderns' sophisticated weaponry, such as throwing spears with a variety of carefully wrought stone, bone and antler tips, made them more successful. And the tools may have kept them relatively safe; fossil evidence shows Neanderthals suffered grievous injuries, such as gorings and bone breaks, probably from hunting at close quarters with short, stone-tipped pikes and stabbing spears. Both species had rituals—Neanderthals buried their dead—and both made ornaments and jewelry. But the moderns produced their artifacts with a frequency and expertise that Neanderthals never matched. And Neanderthals, as far as we know, had nothing like the etching at Blombos Cave, let alone the bone carvings, ivory flutes and, ultimately, the mesmerizing cave paintings and rock art that modern humans left as snapshots of their world.

When the study of human origins intensified in the 20th century, two main theories emerged to explain the archaeological and fossil record: one, known as the multi-regional hypothesis, suggested that a species of human ancestor dispersed throughout the globe, and modern humans evolved from this predecessor in several different locations. The other, out-of-Africa theory, held that modern humans evolved in Africa for many thousands of years before they spread throughout the rest of the world.

In the 1980s, new tools completely changed the kinds of questions that scientists could answer about the past. By analyzing DNA in living human populations, geneticists could trace lineages backward in time. These analyses have provided key support for the out-of-Africa theory. Homo sapiens, this new evidence has repeatedly shown, evolved in Africa, probably around 200,000 years ago.

The first DNA studies of human evolution didn't use the DNA in a cell's nucleus—chromosomes inherited from both father and mother—but a shorter strand of DNA contained in the mitochondria, which are energy-producing structures inside most cells. Mitochondrial DNA is inherited only from the mother. Conveniently for scientists, mitochondrial DNA has a relatively high mutation rate, and mutations are carried along in subsequent generations. By comparing mutations in mitochondrial DNA among today's populations, and making assumptions about how frequently they occurred, scientists can walk the genetic code backward through generations, combining lineages in ever larger, earlier branches until they reach the evolutionary trunk.

At that point in human history, which scientists have calculated to be about 200,000 years ago, a woman existed whose mitochondrial DNA was the source of the mitochondrial DNA in every person alive today. That is, all of us are her descendants. Scientists call her "Eve." This is something of a misnomer, for Eve was neither the first modern human nor the only woman alive 200,000 years ago. But she did live at a time when the modern human population was small—about 10,000 people, according to one estimate. She is the only woman from that time to have an unbroken lineage of daughters, though she is neither our only ancestor nor our oldest ancestor. She is, instead, simply our "most recent common ancestor," at least when it comes to mitochondria. And Eve, mitochondrial DNA backtracking showed, lived in Africa.

Subsequent, more sophisticated analyses using DNA from the nucleus of cells have confirmed these findings, most recently in a study this year comparing nuclear DNA from 938 people from 51 parts of the world. This research, the most comprehensive to date, traced our common ancestor to Africa and clarified the ancestries of several populations in Europe and the Middle East.

While DNA studies have revolutionized the field of paleoanthropology, the story "is not as straightforward as people think," says University of Pennsylvania geneticist Sarah A. Tishkoff. If the rates of mutation, which are largely inferred, are not accurate, the migration timetable could be off by thousands of years.

To piece together humankind's great migration, scientists blend DNA analysis with archaeological and fossil evidence to try to create a coherent whole—no easy task. A disproportionate number of artifacts and fossils are from Europe—where researchers have been finding sites for well over 100 years—but there are huge gaps elsewhere. "Outside the Near East there is almost nothing from Asia, maybe ten dots you could put on a map," says Texas A&M University anthropologist Ted Goebel.

As the gaps are filled, the story is likely to change, but in broad outline, today's scientists believe that from their beginnings in Africa, the modern humans went first to Asia between 80,000 and 60,000 years ago. By 45,000 years ago, or possibly earlier, they had settled Indonesia, Papua New Guinea and Australia. The moderns entered Europe around 40,000 years ago, probably via two routes: from Turkey along the Danube corridor into eastern Europe, and along the Mediterranean coast. By 35,000 years ago, they were firmly established in most of the Old World. The Neanderthals, forced into mountain strongholds in Croatia, the Iberian Peninsula, the Crimea and elsewhere, would become extinct 25,000 years ago. Finally, around 15,000 years ago, humans crossed from Asia to North America and from there to South America.

Africa is relatively rich in the fossils of human ancestors who lived millions of years ago (see timeline, opposite). Lush, tropical lake country at the dawn of human evolution provided one congenial living habitat for such hominids as Australopithecus afarensis. Many such places are dry today, which makes for a congenial exploration habitat for paleontologists. Wind erosion exposes old bones that were covered in muck millions of years ago. Remains of early Homo sapiens, by contrast, are rare, not only in Africa, but also in Europe. One suspicion is that the early moderns on both continents did not—in contrast to Neanderthals—bury their dead, but either cremated them or left them to decompose in the open.

In 2003, a team of anthropologists reported the discovery of three unusual skulls—two adults and a child—at Herto, near the site of an ancient freshwater lake in northeast Ethiopia. The skulls were between 154,000 and 160,000 years old and had modern characteristics, but with some archaic features. "Even now I'm a little hesitant to call them anatomically modern," says team leader Tim White, from the University of California at Berkeley. "These are big, robust people, who haven't quite evolved into modern humans. Yet they are so close you wouldn't want to give them a different species name."

The Herto skulls fit with the DNA analysis suggesting that modern humans evolved some 200,000 years ago. But they also raised questions. There were no other skeletal remains at the site (although there was evidence of butchered hippopotamuses), and all three skulls, which were nearly complete except for jawbones, showed cut marks—signs of scraping with stone tools. It appeared that the skulls had been deliberately detached from their skeletons and defleshed. In fact, part of the child's skull was highly polished. "It is hard to argue that this is not some kind of mortuary ritual," White says.

Even more provocative were discoveries reported last year. In a cave at Pinnacle Point in South Africa, a team led by Arizona State University paleoanthropologist Curtis Marean found evidence that humans 164,000 years ago were eating shellfish, making complex tools and using red ocher pigment—all modern human behaviors. The shellfish remains—of mussels, periwinkles, barnacles and other mollusks—indicated that humans were exploiting the sea as a food source at least 40,000 years earlier than previously thought.

The first archaeological evidence of a human migration out of Africa was found in the caves of Qafzeh and Skhul, in present-day Israel. These sites, initially discovered in the 1930s, contained the remains of at least 11 modern humans. Most appeared to have been ritually buried. Artifacts at the site, however, were simple: hand axes and other Neanderthal-style tools.

At first, the skeletons were thought to be 50,000 years old—modern humans who had settled in the Levant on their way to Europe. But in 1989, new dating techniques showed them to be 90,000 to 100,000 years old, the oldest modern human remains ever found outside Africa. But this excursion appears to be a dead end: there is no evidence that these moderns survived for long, much less went on to colonize any other parts of the globe. They are therefore not considered to be a part of the migration that followed 10,000 or 20,000 years later.

Intriguingly, 70,000-year-old Neanderthal remains have been found in the same region. The moderns, it would appear, arrived first, only to move on, die off because of disease or natural catastrophe or—possibly—get wiped out. If they shared territory with Neanderthals, the more "robust" species may have outcompeted them here. "You may be anatomically modern and display modern behaviors," says paleoanthropologist Nicholas J. Conard of Germany's University of Tübingen, "but apparently it wasn't enough. At that point the two species are on pretty equal footing." It was also at this point in history, scientists concluded, that the Africans ceded Asia to the Neanderthals.

Then, about 80,000 years ago, says Blombos archaeologist Henshilwood, modern humans entered a "dynamic period" of innovation. The evidence comes from such South African cave sites as Blombos, Klasies River, Diepkloof and Sibudu. In addition to the ocher carving, the Blombos Cave yielded perforated ornamental shell beads—among the world's first known jewelry. Pieces of inscribed ostrich eggshell turned up at Diepkloof. Hafted points at Sibudu and elsewhere hint that the moderns of southern Africa used throwing spears and arrows. Fine-grained stone needed for careful workmanship had been transported from up to 18 miles away, which suggests they had some sort of trade. Bones at several South African sites showed that humans were killing eland, springbok and even seals. At Klasies River, traces of burned vegetation suggest that the ancient hunter-gatherers may have figured out that by clearing land, they could encourage quicker growth of edible roots and tubers. The sophisticated bone tool and stoneworking technologies at these sites were all from roughly the same time period—between 75,000 and 55,000 years ago.

Virtually all of these sites had piles of seashells. Together with the much older evidence from the cave at Pinnacle Point, the shells suggest that seafood may have served as a nutritional trigger at a crucial point in human history, providing the fatty acids that modern humans needed to fuel their outsize brains: "This is the evolutionary driving force," says University of Cape Town archaeologist John Parkington. "It is sucking people into being more cognitively aware, faster-wired, faster-brained, smarter." Stanford University paleoanthropologist Richard Klein has long argued that a genetic mutation at roughly this point in human history provoked a sudden increase in brainpower, perhaps linked to the onset of speech.

Did new technology, improved nutrition or some genetic mutation allow modern humans to explore the world? Possibly, but other scholars point to more mundane factors that may have contributed to the exodus from Africa. A recent DNA study suggests that massive droughts before the great migration split Africa's modern human population into small, isolated groups and may have even threatened their extinction. Only after the weather improved were the survivors able to reunite, multiply and, in the end, emigrate. Improvements in technology may have helped some of them set out for new territory. Or cold snaps may have lowered sea level and opened new land bridges.

Whatever the reason, the ancient Africans reached a watershed. They were ready to leave, and they did.

DNA evidence suggests the original exodus involved anywhere from 1,000 to 50,000 people. Scientists do not agree on the time of the departure—sometime more recently than 80,000 years ago—or the departure point, but most now appear to be leaning away from the Sinai, once the favored location, and toward a land bridge crossing what today is the Bab el Mandeb Strait separating Djibouti from the Arabian Peninsula at the southern end of the Red Sea. From there, the thinking goes, migrants could have followed a southern route eastward along the coast of the Indian Ocean. "It could have been almost accidental," Henshilwood says, a path of least resistance that did not require adaptations to different climates, topographies or diet. The migrants' path never veered far from the sea, departed from warm weather or failed to provide familiar food, such as shellfish and tropical fruit.

Tools found at Jwalapuram, a 74,000-year-old site in southern India, match those used in Africa from the same period. Anthropologist Michael Petraglia of the University of Cambridge, who led the dig, says that although no human fossils have been found to confirm the presence of modern humans at Jwalapuram, the tools suggest it is the earliest known settlement of modern humans outside of Africa except for the dead enders at Israel's Qafzeh and Skhul sites.

And that's about all the physical evidence there is for tracking the migrants' early progress across Asia. To the south, the fossil and archaeological record is clearer and shows that modern humans reached Australia and Papua New Guinea—then part of the same landmass—at least 45,000 years ago, and maybe much earlier.

But curiously, the early down under colonists apparently did not make sophisticated tools, relying instead on simple Neanderthal-style flaked stones and scrapers. They had few ornaments and little long-distance trade, and left scant evidence that they hunted large marsupial mammals in their new homeland. Of course, they may have used sophisticated wood or bamboo tools that have decayed. But University of Utah anthropologist James F. O'Connell offers another explanation: the early settlers did not bother with sophisticated technologies because they did not need them. That these people were "modern" and innovative is clear: getting to New Guinea-Australia from the mainland required at least one sea voyage of more than 45 miles, an astounding achievement. But once in place, the colonists faced few pressures to innovate or adapt new technologies. In particular, O'Connell notes, there were few people, no shortage of food and no need to compete with an indigenous population like Europe's Neanderthals.

Modern humans eventually made their first forays into Europe only about 40,000 years ago, presumably delayed by relatively cold and inhospitable weather and a less than welcoming Neanderthal population. The conquest of the continent—if that is what it was—is thought to have lasted about 15,000 years, as the last pockets of Neanderthals dwindled to extinction. The European penetration is widely regarded as the decisive event of the great migration, eliminating as it did our last rivals and enabling the moderns to survive there uncontested.

Did modern humans wipe out the competition, absorb them through interbreeding, outthink them or simply stand by while climate, dwindling resources, an epidemic or some other natural phenomenon did the job? Perhaps all of the above. Archaeologists have found little direct evidence of confrontation between the two peoples. Skeletal evidence of possible interbreeding is sparse, contentious and inconclusive. And while interbreeding may well have taken place, recent DNA studies have failed to show any consistent genetic relationship between modern humans and Neanderthals.

"You are always looking for a neat answer, but my feeling is that you should use your imagination," says Harvard University archaeologist Ofer Bar-Yosef. "There may have been positive interaction with the diffusion of technology from one group to the other. Or the modern humans could have killed off the Neanderthals. Or the Neanderthals could have just died out. Instead of subscribing to one hypothesis or two, I see a composite."

Modern humans' next conquest was the New World, which they reached by the Bering Land Bridge—or possibly by boat—at least 15,000 years ago. Some of the oldest unambiguous evidence of humans in the New World is human DNA extracted from coprolites—fossilized feces—found in Oregon and recently carbon dated to 14,300 years ago.

For many years paleontologists still had one gap in their story of how humans conquered the world. They had no human fossils from sub-Saharan Africa from between 15,000 and 70,000 years ago. Because the epoch of the great migration was a blank slate, they could not say for sure that the modern humans who invaded Europe were functionally identical to those who stayed behind in Africa. But one day in 1999, anthropologist Alan Morris of South Africa's University of Cape Town showed Frederick Grine, a visiting colleague from Stony Brook University, an unusual-looking skull on his bookcase. Morris told Grine that the skull had been discovered in the 1950s at Hofmeyr, in South Africa. No other bones had been found near it, and its original resting place had been befouled by river sediment. Any archaeological evidence from the site had been destroyed—the skull was a seemingly useless artifact.

But Grine noticed that the braincase was filled with a carbonate sand matrix. Using a technique unavailable in the 1950s, Grine, Morris and an Oxford University-led team of analysts measured radioactive particles in the matrix. The skull, they learned, was 36,000 years old. Comparing it with skulls from Neanderthals, early modern Europeans and contemporary humans, they discovered it had nothing in common with Neanderthal skulls and only peripheral similarities with any of today's populations. But it matched the early Europeans elegantly. The evidence was clear. Thirty-six thousand years ago, says Morris, before the world's human population differentiated into the mishmash of races and ethnicities that exist today, "We were all Africans."

Guy Gugliotta has written about cheetahs, Fidel Castro and London's Old Bailey courthouse for Smithsonian.