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.