We can be very comfortable in saying that all non-Africans had their origins in an African population whose closest living relatives are now centered in East Africa, more or less in the region from Ethiopia through the Rift Valley, where mtDNA haplogroup L3 from which all Eurasian specific mtDNA types (which are inherited matrilineally) arise.
There are several other mtDNA L haplogroups. All of the significant mtDNA haplogroup L subhalogroups, except L2 and L3 are found mostly in hunter-gatherer populations of Bushmen (aka the Khoisan) and Pygmies, and there are linguistic remnants in Bantu language populations of East Africa (whom we know adopted the Bantu languages no earlier than the last few hundred to couple thousand years) as well as genetic indicators of people with genetic connection to Bushmen and Pygmies, that suggest that populations of Bushmen once extended all the way to East Africa, although the Bushmen and Pygmies now live in Southern Africa and the West African tropics respectively.
We also know from matrilineal and patrlineal DNA evidence that mtDNA and Y-DNA haplogroups associated with Bushmen and Pygmies are the most and second most basal branches of the uniparental DNA family tree respectively. These relict African hunter-gatherer populations are the modal populations in Y-DNA haplogroups A and B which are the most basal Y-DNA haplogroups.
All Eurasians Y-DNA haplogroups, and Y-DNA haplogroup E which is predominantly African today, are branches of Y-DNA macro-haplogroup B.
The predominant Y-DNA haplogroup in Africa is E1b1 and a new study has refined our understanding of the branching family tree of that patrilineally inherited trait. Its bottom line is that new discoveries regarding how branches of the E1b1 family tree previously believed to be independent are related to each other "strongly supports the hypothesis that haplogroup E1b1 originated in eastern Africa." Eastern Africa is the geographic location that provides the most plausibe source for the roots of the Y-DNA genetic tree given the current dispersal patterns of the branches when arranged properly.
The inference, supported by the admittedly shaky evidence of the mutation rate estimated ages of the lineages in question, is that modern humans radiated out from East Africa not only to Eurasia, but also to West Africa and Southern Africa at roughly the same times, give or take thirty thousand years or so, with the highest order lineages within mtDNA haplogroup L possibly arising in subpopulations within East Africa prior to their dispersal or not long afterwards.
This is hardly surprising, because it lines up rather neatly with the fact that the oldest hominin fossils in the world, but modern human and archaic pre-modern human are found in Eastern Africa.
Now, E1b1 is not the bottom of the Y-DNA tree. Indeed, it is quite a few mutations removed even from the basal splitoff of Y-DNA haplogroup E from Y-DNA haplogroup DE. More basal examples of the Y-DNA E lineage, and even of the pre-Y-DNA E lineage called haplogroup DE are found in West Africa, and if modern humans originated in West Africa there is good reason to think that the evidence of that fact might not survive, because places that are periodically hot and wet create poor conditions for preserving bones and artifacts, and places that are constantly inhabited over long periods of time with all sorts of climate change can get muddled. Similarly, if the Khoisans originated in West Africa and migrated early on from there to Eastern Africa before ending up in Southern Africa there is really no way that we could distinguish that scenario from an Eastern African origin scenario with existing data.
But, while the evidence that we have is not definitive enough to say with great confidence that "Eden" was in Eastern Africa, rather than Western Africa, for example, it is definitive enough to say with considerable confidence that the vast majority of Africans living today probably have significant Eastern African ancestry. The paper notes that:
Haplogroup E1b1 now contains two basal branches, E-V38 (E1b1a) and E-M215 (E1b1b), with V38/V100 joining the two previously separated lineages E-M2 (former E1b1a) and E-M329 (former E1b1c). Each of these two lineages has a peculiar geographic distribution. E-M2 is the most common haplogroup in sub-Saharan Africa, with frequency peaks in western (about 80%) and central Africa (about 60%). The same haplogroup is also present in North Africa, although at a lower frequency (usually below 10%) –. Haplogroup E-M329, on the other hand, was observed almost exclusively in eastern Africa , [12 and R.S. unpublished data], where E-M2 is virtually absent.
Patriline E-M2 seems to correspond fairly closely to to matriline L2, while patriline E-M329 seems to correspond closely, but not quite so closely, to matriline L3, and these two patrilines which have a common origin, and these two matrilines (with L3 being mostly closely related to L2 among the African mtDNA haplogroups) include most Africans alive today. It is natural to assume that the corresponding patrilines and matrilines expanded together as parts of a single population, although there are certainly plenty of historical examples of patriline and matriline source populations becoming dissimilar due to conquest or caste or some other factor of that kind.
If the two Y-DNA lineages and mtDNA lineages do indeed correspond to each other and were parts of the same populations, then the common Easterns African origin of the E1b1 lineages must also have been the place of origin of the mtDNA L2 and L3 lineages.
Thus, we have a pre-history scenario where all Eurasian and the lion's share of Africans arose from founding populations in East Africa that were in existence much later the time of Y-DNA Adam and mitochondrial Eve, and fairly close in time to each other on the order of several tens of thousands of years, still a broad range of time, but a much narrower one. And, this time during which each of the founder populations who descendants went on to become almost all modern humans were each present in Eastern Africa in a time period much more recent (by something on the order of a factor of two or three) than the date that marks the common ancestors of all modern humans.
On the other hand, since the splits that separate the predominantly non-African Y-DNA haplogroups CF and D from the predominantly African Y-DNA haplogroup E take place many mutations before predominantly African Y-DNA haplogroup E-V38, one can say with some confidence that there was population structure that separated the Eurasian founding population from the predominant founder population of Africans alive today many thousands of years before the predominant founder population of Africans alive today emerged from Eastern Africa to eventually become predominant across the continent. (Note that I have intentionally not provided any clarity on where precisely the Eurasian founder population lived at the time that it became genetically distinct, which could be in Africa, in the Near East, in South Asia, or perhaps even other places.)
If one assumes that the non-African to African split happened sometime close to the Out of Africa founder population's migration (probably at least 75,000 years ago, as we can't be sure that the first Out of Africa founding population in the Levant and the founding population of the people that migrated along the Southern Coastal route of Asia was the same one, although that would be plausible), then that means that most non-Africans in West Africa have genetic roots in Eastern Africa quite a bit more recent than then (most Southern Africans, although certainly not all, have some genetic roots in the Bantu population near the Cameroon-Nigeria border and trace their roots to Eastern Africa only via that source Bantu population). The best estimates of the dates when the pygmy population starts to split, perhaps due to disruption from new migrating populations, is around 20,000 years ago. My gut instinct is to associate the E1b1 expansion out of Eastern Africa with the Sahel and Ethiopian Highlands Neolithic (which was more or less independent of the Near Eastern Neolithic and may even have started a little sooner), or perhaps a few thousand years before then, but I can't definitively support that conclusion and there are other plausible scenarios.
The potential to cross-calibrate mtDNA mutation rate date estimates, and Y-DNA mutation rate date estimates, to the extent that correspondences can be made, also offers the potential for making both kinds of dating more accurate.