The Nefud or An Nafud is a desert that sits on the North of Arabia Peninsula. Last year, tireless archaeologist Michael Petraglia published a paper on a newly found archaeological culture from that, now so arid, region (see here) dated to c. 75,000 years ago.
|Location of the Nefud site of Jubbah (fig. 16 of present study)
It was pay per view however. This new release he has chosen instead the open access journal by default, PLoS ONE:
Michael D. Petraglia et al., Hominin Dispersal into the Nefud Desert and Middle Palaeolithic Settlement along the Jubbah Palaeolake, Northern Arabia. PLoS ONE 2012. Open access → LINK [doi:10.1371/journal.pone.0049840]
The Arabian Peninsula is a key region for understanding hominin
dispersals and the effect of climate change on prehistoric demography,
although little information on these topics is presently available owing
to the poor preservation of archaeological sites in this desert
environment. Here, we describe the discovery of three stratified and
buried archaeological sites in the Nefud Desert, which includes the
oldest dated occupation for the region. The stone tool assemblages are
identified as a Middle Palaeolithic industry that includes Levallois
manufacturing methods and the production of tools on flakes. Hominin
occupations correspond with humid periods, particularly Marine Isotope
Stages 7 and 5 of the Late Pleistocene. The Middle Palaeolithic
occupations were situated along the Jubbah palaeolake-shores, in a
grassland setting with some trees. Populations procured different raw
materials across the lake region to manufacture stone tools, using the
implements to process plants and animals. To reach the Jubbah
palaeolake, Middle Palaeolithic populations travelled into the
ameliorated Nefud Desert interior, possibly gaining access from multiple
directions, either using routes from the north and west (the Levant and
the Sinai), the north (the Mesopotamian plains and the Euphrates
basin), or the east (the Persian Gulf). The Jubbah stone tool
assemblages have their own suite of technological characters, but have
types reminiscent of both African Middle Stone Age and Levantine Middle
Palaeolithic industries. Comparative inter-regional analysis of core
technology indicates morphological similarities with the Levantine Tabun
C assemblage, associated with human fossils controversially identified
as either Neanderthals or Homo sapiens.
In this study, they report the oldest known Arabian occupation by any kind of humans c. 211,000 years ago:
Though so far a small excavated stone tool assemblage, the recovery of
28 artefacts in a deposit dated to 211±16 ka represents the oldest
reliably dated occurrence in the Arabian Peninsula. We tentatively
associate this assemblage with the Middle Palaeolithic on the basis of
the age of the technology and the recovery of two Levallois flakes.
Although we cannot be certain of the species that manufactured the
artefacts, we note that the lithic assemblages were produced at a time
corresponding with the origin of Homo sapiens in Africa based on mitochondrial DNA  and nuclear genomic  age estimates and fossil finds , .
The early JQ-1 artefacts also correspond with the upper age range
limits of the Acheulo-Yabrudian and the Zuttiyeh fossil, potentially
indicating the presence of archaic hominins  in Arabia, and possibly early representatives of the Neanderthals .
However the main findings are still from the 75,000 years old layer, whose cultural affinities and possible maker species are pondered. The most visually accessible result is a PC analysis:
|Fig. 17 (Jebel Qattar and Jebel Katefeh are the Jubbah Lake sub-sites)
Notice how the Jubbah sub–sites (the two Jebels) fall between two Levantine Mousterian sites: El Wad and Tabun C, attributed to Neanderthals. So it is very likely that this colonization represents an expansive attempt by West Asian Neanderthals.
Possibly related is the also recent finding (Delagnes 2012) of Mousterian in Yemen, dated to c. 55,000 BP. Therefore it would appear that after the expansion of Homo sapiens in Arabia, eventually leading to the colonization of Southern and Eastern Asia, as well as Near Oceania, there was an expansive tendency of Neanderthals as well, which may have helped to partly erase the genetic remnants of the out-of-Africa episode in the most fertile parts of Arabia Peninsula.