Not every gene that makes us human (if you look at us from a genetic point of view) comes from Africa, but the area around Ethiopia can be called the Cradle of the Human Gene Pool.
All humans on the planet trace their ancestry back to a small group of humans living in Ethiopia around 200-265,000BP. The first fossil human bones date to around 200,000BP (near Omo, Ethiopia) and recently, human tools were found nearby dating even further back - to around 265,000BP. Many archaeologists have been puzzled by the lack of any significant behavioral change at around the time that humans arose, but now, it turns out, we're finding good evidence of those new human behaviors. There's no evidence that we're performing music or even that we're speaking languages like we have today, but there are significant changes:
Most modern language capacities are in place - we could talk circles around Neanderthal and Homo erectus and Homo ergaster.
We have multi-part tools. Doesn't sound like a big deal, but it's more than 2 million years from the first stone tools to making hafted tools and such.
We're expanding quickly out of Ethiopia, compared to previous versions of humans.
For a long time (the entire time I was in university and most of my teaching career), the oldest human living sites in Africa seemed to be in South Africa, like the famous caves at Swartkrans. From around 135,000BP onward, South Africa was well-populated, a hotbed of human activity and innovation. That's because it is on the edge of the one of the world's largest natural game preserves - the Great Plain of the Serengeti. A natural game preserve is a place where mountains and hills form natural boundaries that tend to hedge the game in. The Serengeti region is huge and the humans who first found it, with their newly invented spears and other technologies, were very likely the "richest" humans on Earth at the time. The general region is often referred to in anthropology literature as Swaziland, because the contemporary nation of Swaziland is roughly at the center of this region. Homo sapiens style tools, often called "Levallois technology" are found in Swaziland all the way back to 200,000, although the fossil record starts somewhat later.
The point is that humans began to explore and fill up Eastern Africa by 200,000BP. By 135,000BP, people had distributed themselves along the Mediterranean Coast of North Africa and into the Levant (the Middle East). This is our first diaspora, our first burst of population growth (and resource use). People did not look then as they do now (a complex topic on which more and more data is constantly gathered), but to say they look "generally African" is not terribly misleading. There's a great DVD on this topic from National Geographic (from the Human Genome project).
Some people headed out of Africa toward India and Southeast Asia, but no one went to Europe at this time.
Interestingly, genes from these early African humans have been found in contemporary Australian aborigines, who certainly arrived in Australia by 60,000BP and whose ancestors were in the foothills of the Himalayas, in India, by 90-100,000BP.
There is one truly fascinating fact, to me, about where these first humans ended up. It turns out that by 125,000BP, FMHS (that's us) had located virtually every major source of flint in Africa and the Middle East.
Flint doesn't appear just anywhere. If you or I had to go find some, we'd have quite a time finding it. With satellites and stuff, it's easier to find, but back then, many different mental and practical abilities were involved in finding flint.
South Africa is one of the world's major flint-bearing regions (so is Europe, but more of that later). Flint was the oil of its day. Learning to use flint in a multitude of ways revolutionized human life. By 125,000BP, the following tools and items (mostly made of flint or made with tools made of flint) appeared for the first time on Earth (some of these appeared somewhat earlier, but I'm trying to summarize what happened up until around 100-135,000BP):
The flint spearhead on a spear (made with flint raspers to ensure a truly balanced and symmetrical form; the rasper had been in use for quite some time, but not always made of flint - flint is sharper). The spears were put together using cooked glues, usually from bitumin (tar).
Flint firestrikers. Possibly the most important tool in the toolkit.
The flint drill. Used for drilling holes in wood, stone, shell, bone and other materials to make such goods as ladders, bridges, boats, necklaces.
Flint punchers, burnishers and awls. For leatherworking, to make travois, backpacks, clothing, sandals, other kinds of shoes.
Notably absent: there were no bows and arrows - that's much much later.
Still, using my cultural imagination (and looking at how many humans and how farflung they are by 125,000), we see a world that looks very familiar. I believe people were traveling quite a bit, and that they had boats of some kind. Neither wood nor fiber artifacts are likely to survive for 100,000 years or more - especially if they get wet - so we may never know. However, the coastal dwelling preferences of early humans make me believe that they had canoes. The distance between their early settlements argues for a water-based method of transport, for one thing.
One big settlement was in modern Algeria, near flint mines. Flint mining (as opposed to ground collection without having to mine) began in Algeria by at least 125,000BP. Algeria has bigger deposits than the next region, which is a small area in Egypt, but nothing compared to the flint resources of Swaziland.
In Swaziland, by 125,000, there is good evidence for the use of ladders, to climb down sheer cliff faces to do flint mining, and for bridges. They had to transport all the flint somehow, and that flint shows up all over Africa eventually. While there is no evidence of symbol-use that bore specific meanings, people did begin to use red ochre to paint their bodies, including the bodies of the dead. The first burials show up at this time, providing some early evidence of religious custom or belief. If the Africans of Swaziland did indeed use ochre to mark things, none of the markings survive, but the ochre itself (which is a soft material) was sometimes incised (by 100,000BP) with what look like tally marks or some other marks indicating meaning. Burials included grave goods, and beautifully made shell necklaces are found in Algeria and Israel from this time period.
The population was densest in South Africa, but people did not move around the horn of Africa up into West Africa until a much later date (the extreme dryness of the Kalahari desert probably blocked them at that time). People didn't move south past Algeria much either - rainforest was difficult to adjust to, but people did find new natural game preserves in what is now the Sahara - it was grasslands back then.
Life was good. When people can get enough to eat and have a sustainable lifestyle, life is good. The population didn't grow very quickly in those days, but as it did grow, people moved out of more crowded places (like Swaziland) and into less crowded ones, eventually distributing themselves from Algeria east to Cambodia and Vietnam, but avoiding colder, northern places and very hot, wet places (interior rainforests for example). Eventually, the world would grow crowded enough that new places would be sought out - although, as I will propose, there was more to this new diaspora than simply "it was too crowded." It was in the next phase - the second movement out of Africa - that Europe and Northern Eurasia become populated, which is where I'm heading.