Science is making good progress at developing consensus story based upon multiple lines of evidence of the pre-history of modern humans outside Africa (e.g. DNA, archaeological artifact discoveries, megafauna extinctions).
The core story is that a small subset of the modern human African population (a group with a population of perhaps ten thousand or less) left Africa, rapidly expanded and are the ancestors of all ancestral non-African humans. The Out of Africa event or events took place at one or the other end of the Red Sea, no more recently than 50,000 years ago and quite possibly 100,000 years ago or even 200,000 years ago.
Evidence for the presence of modern humans outside Africa significantly more than 100,000 years ago, is pretty much limited to the isolated Dali remains in China discussed below, whose identification as at least partially modern human is not terribly solid. It would not be terribly surprising for later research to determine that either the classification or the dating of these remains was incorrect. An older date (e.g. 300,000 years ago) would be suggestive of a pure homo erectus or Neanderthal-Homo Erectus hybrid whose similarities to modern humans were strictly a product of convergent evolution, and would heighten the possibility of a homo erectus extinction event before modern humans arrived outside some isolated refugia like the island of Java. A younger date (e.g. 65,000 years ago) would suggest a modern human-Homo Erectus hybrid born at a time more consistent with other evidence for the appearance of modern humans in the area. The date currently assigned to Dali is based on an Ox tooth found in the proximity of the remains and itsn't clearly inconsistent with the surrounding strata, but is hardly a rock solid direct dating of the remains either. Redating ancient human remains findings isn't particularly unusual unless the original date was based on some virtually irrefutable evidence such as a direct carbon dating of bone material.
Recent discoveries have complicated this scenario slightly. Early modern human populations (either a single one, or each of a couple of them) co-existed and admixed with Neanderthals in small proportions before dispersing across Eurasia, leaving an average of 2.5% Neanderthal ancestry in a somewhat complex scenario that leaves no modern humans with a Neanderthal matriline or patriline ancestor. Proto-populations of Melanesians, and possibly some neighboring populations, co-existed and admixed in fairly substantial proportions (perhaps 7% of modern descendants) with a population genetically similar to an ancient Denisovian DNA sample recovered from an archaic hominin. Apart from these instances of admixture in the last 100,000 years or so, a common modern human ancestor probably split from the ancestors of Neanderthals and Denisovians 400,000 to 1,000,000 or more years ago.
The bulk of human evolution took place entirely in Africa there were a melange of archaic hominin species at many steps of an evolutionary tree whose exact relationship to each other and classification is disputed, even though the general trend is not. Our closest extant primate relative species are the Chimpanzee and Bonobos of Africa which diverged from a common ancestor with us at a time period on the order of 4 to 8 million years ago.
Modern humans were not, however, the first wave of hominins to leave Africa. The two most notable previous waves were Homo Erectus and the Neanderthals. There are also two isolated post-Out of Africa archaic human remain sites whose place in the overall picture of human evolution is unclear, one of which has yielded ancient DNA that appears to have introgressed into Asian populations, particularly Melanesians.
The first archaic hominin found outside of Africa, stating sometime between one and two million years ago is Homo Erectus. In Asia, we have Homo Erectus fossils on the island of Java in Indonesia (at three sites), in Vietnam (at one or two sites), in China (two sites) and in South Asia (at one site). With recent redatings, it now appears that all of these Asian specimens are apparently from the early Paleolithic (up to about 300,000 or 400,000 years ago). We also have Homo Erectus fossils in Europe and Africa from the early Paleolithic. Homo Erectus doesn't appear to have reached outer Oceania, Australia, Japan, the Andaman Islands, the Philippines or the Americas.
We have evidence for Neanderthals in Europe and probably the Near East and South Asia starting the the Middle Paleolithic (about 300,000 years ago) until about 30,000 years ago. Neanderthals appear to have rapidly replaced Homo Erectus within its range and there are numerous sites with Neanderthal remains over a wide time period and geographic range. There are something on the order of half a dozen Neanderthal ancient DNA samples that have been recovered.
Dali, Denisovians, Homo Florensis and Other Archaics
We have a single case, probably from 209,000 years ago in China, called Dali, that looks something like a hybrid Homo Erectus/modern human whose proper classification is uncertain. Dali is a couple of hundred thousand years, at least, after the next more recent Asian hominin, but, the next oldest modern human remains anywhere in Asia are more than a hundred thousand years older.
We have fragmentary remains at a single location of a late Middle Paleolithic robust archaic hominin, in the Altai Mountains of Siberia about 40,000 years ago, that is called Denisovian and has yielded ancient DNA samples. It may be a remote branch of Neanderthal, a hybrid of Neanderthal and Homo Erectus, or a branch of Homo Erectus from about 40,000 years ago. Genetic similarities with Melanesians suggest that they one had a much wider distribution.
We have an example at a single location, from perhaps as recent as 18,000 years ago in Flores, sometimes called hobbits, that could be from a relict population of dwarf Homo Erectus (or perhaps dwarf Denisovian).
We have eviendence very early archaic hominins in Europe and Africa in that region that could be called their own species, or could be lumped with Homo Erectus or the Neanderthals respectively, and a few that could be hybrids of Neanderthals and modern humans.
Do Modern Humans Populations Have DNA Traces Of Other Archaic Human Populations And If So, Where Would We Expect To Find Them?
It wouldn't be unthinkable, given the evidence of Neanderthal and Denisovian admixture with modern humans, that there may have been other archaic homininshominins in proportions of the same order of magnitude that was actually observed when ancient Neanderthal DNA was first described and compared to modern human DNA, was predicted a number of years before it was observed from these genetic patterns. Similar methods, looking for a residual of the archaic hominin admixture proportion after contributions to two know ancient DNA sources are backed out, should be able to put meaningful boundaries on how much of our DNA could be attributed to other kinds of ancient admixture.
The fossil record and our knowledge of modern human and archaic hominin population history puts some definite bound on how much more we should expect to find. While I wouldn't be surprised if we found new archaic admixture sources in one or more African subpopulations, I would be surprised if we found many more in non-African populations.
There is no evidence that modern humans and non-Neanderthal archaic hominins ever co-existed in Europe or the Near East. These appear to have been exclusive Neanderthal ranges when modern humans left Africa, and that range for very large geographically. There is also no evidence for Neanderthal populations in most of Asia at any time, and we know what to look for and where to look for it, when searching for Neanderthal traces from experience in Europe.
The fact that DNA from Denisovian remains found in the Altai Mountains is found at levels much more elevated in Melanesians than in other populations suggests several things.
First, the Denisovian population must have had a range as a fairly genetically uniform species that extended from Siberia to the coastal route taken to reach Melanesia in the late Middle Paleolithic era. Yet, typically, there is one one species in the kind of ecological niche that they held at one time, so there were unlikely to be other hominin species present at the same time as the Denisovians whom we know had the right timing, outside areas like islands or mountain valleys that would have been ecologically separated refugia from the rest of the pre-modern human hominin population.
Second, if there were Denisovian populations in mainland Asia that admixed with modern humans, it is likely that it had disappeared due to admixture and extinction not long after contact with the first wave of modern humans that they encountered like the Neanderthals. In the case of Melanesians, there were no subsequent waves of migration to dilute that contribution for something on the order of 40,000 years and the initial population might very well have reached a severe bottleneck at the time of first contact on the literal frontier of human settlement. But, in mainland Asia, subsequent waves of modern human populations, which appear to have replaced the original populations of mainland Asia to a great extent both in waves before and waves after the Neolithic revolution, probably tremendously diluted any archaic human admixture contribution to the first wave population.
Third, even if modern humans did admix with modern humans in ecologically isolated refugia like Flores island, it seems unlikely in the time frame of from modern human appearance to complete archaic hominin extinction that these refugia would have been sources for major population expansions of admixed modern humans. Population expansions would be expected to have their sources in large non-isolated areas, not ecological cul-de-sacs.
Thus, undisovered archaic populations seem most likely to have been present in Africa, where there was much more hominin diversity, and in places outside Africa, seem most likely to have been present in places outside the Neanderthal range that could have formed isolated refugia for archaic hominins like islands and mountain valleys that have not been profoundly diluted by subsequent post-archaic hominin extinction migrations into them.
Some instances of still undiscovered ancient admixture in the genome, even if they are out there, may be confined to single groups of African hunter-gatherers, for example, or people in a few villages in the Caucasus mountains, but seem far less likely to be discovered, for example, in the Han Chinese, or the Japanese, whose predominant ancestors probably didn't arrive anywhere close to their present territories at times when there were still archaic humans in the world.
Even if there are eight different species of archaic hominin that admixed with modern humans in Africa, it is unlikely that more than two or three of those species admixted with ancestors of the modern humans who left Africa or experienced major demographic expansions within Africa with the advent of food production. Archaic human ancestry that made its way into the ancestors of the Bantu population are probably detectable. Archaic human ancestry that made its way only into one or two out of many Khoisan tribes may not be possible to detect, and quite possible may have been culled from the gene pool as some Khoisan tribes survived and others did not over time.
There is also not much evidence for large, diversified populations of non-Neanderthal hominins outside Africa, in the post-Out of Africa era. Homo Erectus seem to have a fairly consistent physical form and not very rapidly evolving tool kit for most of the hundreds of millenia and multi-continental range where they are observed. The DNA admixture evidence seems to suggest something similar about the Denisovians. Like modern humans who left Africa, the Homo Erectus population that left Africa probably had only a small subset of the amount of genetic diversity found in the entire archaic hominin, or even Homo Erectus population of Africa at that time.
Also, it is fair to guess that Homo Erectus, which was displaced by Neanderthals in West Eurasia when they competed and doesn't seem to have had much of an ecological impact, was probably a less effective hunter-gatherer and hence probably maintained a lower population density, than Neanderthals who appear to have had more sophisticated tools and form of social organization. Given how sparse we know the Neanderthal population to have been based on inferences from ancient DNA, i.e., on the order of the ten to twenty thousand for all of Europe in perhaps three only moderately overlapping regional subpopulations, the number of Homo Erectus out there that modern humans could have encounted outside the Neanderthal range may have been pretty modest and unimpressive as competition relative to the much more sophisticated hunter-gatherers who made up the modern human population. The likely very low population numbers for Homo Erectus, perhaps in the high single digit thousands for all of Asia when modern humans arrived on the scene, also would place significant limits on their mutation rates and ability to maintain diversified subtypes, and would also place significant limits on the extent to which they could impact a probably considerable higher population density modern human hunter-gatherer population.
Uniparental Genetic Evidence For An Out of Africa Scenario
All modern humans share a common ultimate maternal ancestor and a common ultimate paternal ancestor in a time frame generally consistent with the appearance of anatomically modern humans.
All non-African modern humans share one of two maternal ancestors who come from one branch of the tree of matrilineal ancestery found in Africa. All non-African modern human men share one of four paternal ancestors who come from branches of the tree of patrilineal ancestery ultimately rooted in Africa. The time frame in which these ancestors became distinct is generally consistent with the timing of an Out of Africa event.
The matriline descendants of all modern human women outside Africa can be traced via mtDNA which passed from mother to child, sometimes with mutations, to two individuals (line "M" and "N"), and it is not clear if matriline descendants of both women were part of a single original Out of Africa group, or if their descendants represent two separate Out of Africa waves. All of the matrilineal descendants of these two individuals in Africa today (mostly in matrilines called "M1" and "U6" in North Africa and East Africa) appear to have been back migrants from Eurasia probably from sometime in the last 8,000 years. None of the other major African matrilines (labelled "L") left Africa until the historic era or not long before that era.
Both M and N are matriline descendants of the African matrilineal ancestors called "L3", with most Africans belonging to matrilines, L0, L1, L2 and L3 (additional matrilines in the L group have been named based on discoveries of small African populations). Currently, the members of matriline L3 most closely related to non-African matrilines are found in the highest frequencies in East Africa.
All of these African matrilines can be traced to a single female ancestor sometimes called mitchodrial eve.
Patrilineal descendant is traced using the non-recombining part of the Y-chromosome which is passed from father to son and sometimes mutates before being passed on again.
Non-Africans likewise trace descendant from two patrilines, "CF" (with only the "F" part accounting for the patrline ancestry of almost all Europeans and the "C" part largely restricted to Asia, Oceania and the Americas) and "DE" (with "E" part of the latter patrline including a large share of all modern Africans, and a quite small share of all non-Africans geographically near Africa, who probably left Africa long after the Out of Africa event, and the "D" part having a curious distribution that includes Tibet and Japan but has big gaps in between areas of concentration). These patrilines can be traced to a common patrilineal ancestors shared with exclusively African patriline "B". All of these patrilines share a common ancestor with the paternal ancestor of all members of exclusive African patrline "A", sometimes called Y-DNA Adam.
The "C", "D" and "E" patrilines probably made their way out of Africa in migrations that did not overlap with each other. The "F" patriline (which probably emerged as a distinct line at least 45,000 years ago) probably had a population that did not overlap with the "D" patrline (which probably took place at least 30,000 years ago), and would have been much earlier than the migration "E" patrilines (which probably took place no more distantly in the past than the last 18,000 years). The "C" and "F" patrline probably became distinct from each other sometime after the Out of Africa population became distinct from the remaining African population. The "D" and "E" patrilines probably became distinct somewhere in Africa not long before ancestors of the lion's share of modern members of the "D" patriline left Africa. The break between the CF and DE patrilines is probably at least as ancient as the Out of Africa event and could reflect an even older population structure within Africa itself prior to the Out of Africa migration.