In antiquity ostriches and lions roamed the Syrian desert. The cheetah even still clings to a tenuous existence in the fastness of the central Iranian desert. The point being that the new finding of African modern human remains on the southeast fringe of Arabia ~85,000 years ago shouldn’t be too surprising. Old modern(ish) looking humans date to 73,000 years before the present in Southeast Asia. Modern-like ancestry can be found in eastern (Altai) Neanderthals dating to ~100,000 years ago. And the earliest humans may have arrived in Australia 65,000 years ago.
These dates are important because the genetic results indicate that much of the population divergence of modern Eurasian, Amerindian, and Oceanian peoples dates to the period between 50 to 60 thousand years ago. This was the classic epoch for the emergence of “behavioral modernity,” and the older models of “Out of Africa” which posited a rapid explosive demographic growth after a punctuated speciation even in East Africa ~60,000 years ago.
Today with remains such as Ust’-Ishim man, we can peg the admixture of Neanderthal into modern Eurasians 52,000 and 58,000 years ago. About the same period that the preponderance of the ancestry of modern Eurasians and peoples of Australia and the Americas expanded across the world, as noted above.
Most peoples in Western and Southern Eurasia also have substantial ancestry from another group which doesn’t seem to have much Neanderthal ancestry at all, the “Basal Eurasians” (BEu). This population obtained its name from the fact that it was hypothesized to have diverged from the common ancestors of northern Eurasians (the Pleistocene peoples of Europe and Siberia), eastern Eurasians, the ancestors of the Amerindians, and Oceanians, before these groups moved on and then separated (i.e., proto-Melanesians are closer to Pleistocene European hunter-gatherers than they are to BEu). These facts suggest proto-BEu was a distinct population >60,000 years ago.
Because of the distribution of Neanderthal admixture across so many groups relatively evenly it probably came from a single major admixture event. Geography tells us that the most likely area of this admixture would be somewhere in the northern area of West Asia.
This implies that BEu was probably resident in the southern area of West Asia, and possibly into North Africa. We do not have any samples which are “pure BEu.” Ancient agriculturalist samples from the western Near East and the eastern Near East are high in BEu ~10,000+ years ago, but these populations are still substantially mixed with a population with affinities to Mesolithic Western European hunter-gatherers (WHG). Fu et al. 2016 use a Pleistocene transect to infer that this affinity between Near Easterners and Europeans dates to the period after ~15,000 years before the present. I presume that this late Pleistocene period was when BEu was admixed away as a pure population by an expanding hunter-gatherer culture with a nexus in Southeast Europe and into Anatolia and the trans-Caucasian region.
The recent Arabian find makes sense I think in the context of BEu and other such populations, which had diverged from the Africa metapopulation ~100,000 years ago, but had not pushed further north and east, and so mixed with Neanderthals.
But what about the older modern human remains which are showing up in eastern Eurasia? I think it is entirely likely that these populations left only a little bit of an imprint in modern groups. A paper from a few years back reported having detected such an admixture in Oceanians. The first ancient genome we have from eastern Eurasia >60,000 years ago that is from a modern human will probably yield much more satisfying results.
The big dynamic looming over the likely existence of anatomically modern human range on the edge of Africa in Arabia is that for several hundred thousand years modern humans existed within Africa as a metapopulation. The proto-Out-of-Africa population can only be understood as part of this broader metapopulation. ~100,000 years before the present humans, inclusive of Neanderthals, Denisovans, and modern humans, our species was probably defined by a set of distinct metapopulations. We know that there was gene flow between these metapopulations, but the strong evidence of purifying selection of Neanderthal and Denisovan ancestry in modern human genomes tells us that this gene flow was minimal enough that biological incompatibilities were beginning to build up and the groups were on their way to speciation as defined by the biological species concept.
There is no evidence of this between any modern populations, even the most diverged (e.g., the Khoisan, who carry Eurasian and African agriculturalist genetic material). This means that within the modern human metapopulation gene flow was sufficient to prevent incompatibilities from developing due to isolation. That being said, with the oldest (proto-)modern human skull dating to ~300,000 years, and likely discernible population structure between various African lineages going beyond 200,000 years ago, there are lots of distinct modern human groups with very long histories within Africa and on its periphery.
The earliest point that you could probably say non-African humans diverged from any African (Sub-Saharan) populations is ~100,000 years ago (and this is probably a bit too generous). A conservative estimate would suggest that modern human lineages were emerging within Africa 200,000 to 300,000 years ago. So most of modern humanity’s existence has been within Africa.
The non-African populations descend from a group which underwent a period of reduced population size vis-a-vis all the African groups. But one thing I think is important to remember is that this was probably not exceptional. We know now that over the past 5,000 years African population genetic structure has been reshaped by events such as the Bantu expansion. But there were surely small and marginal groups with low effective population sizes within Africa that either went extinct or were absorbed by other populations.
The difference in the non-African population is that it was on the edge of the modern human range, and likely occupied territory that was relatively isolated from other modern humans due to the dry nature of the Sahara during most of the Pleistocene. This prevented its absorption into more numerous groups of modern humans further south and to the west. And the strong cultural and genetic barriers with the Neanderthals probably limited gene flow as well.
But even in the inclement conditions of North Africa and West Asia for most of the past 100,000 years, modern humans may have had a larger effective population size than archaic Eurasian hominins. And with this larger effective population size, one can imagine that greater cultural creativity and genetic robustness to dynamics such as population declines gave the modern humans a long-term advantage. In this context, the existence of modern human remains in a diverse array of places across warmer areas of Eurasia before 60,000 isn’t that surprising. And, the demographic wave that swallowed Neanderthals and Denisovans probably swallowed the earlier modern humans who ventured into eastern Eurasia before 60,000 years ago!