The Empty Quarter (or Rub' al Khali) of the Arabian Peninsula is the largest continuous sandy desert in the world. It has been known for several decades that Late Pleistocene and Holocene deposits, representing phases of wetter climate, are preserved there. These sequences have yielded palaeontological evidence in the form of a variety of vertebrate and invertebrate fossils and have been dated using various radiometric techniques. However, evidence for human presence during these wetter phases has until now been ephemeral. Here, we report on the first stratified and dated archaeology from the Empty Quarter, recovered from the site of Mundafan Al-Buhayrah (MDF-61). Human occupation at the site, represented by stone tools, has been dated to the later part of Marine Isotope Stage (MIS) 5 using multiple luminescence dating techniques (multigrain and single grain OSL, TT-OSL). The sequence consists primarily of lacustrine and palustrine sediments, from which evidence for changing local environmental conditions has been obtained through analysis of fossil assemblages (phytoliths and non-marine molluscs and ostracods). The discovery of securely-dated archaeological material at ∼100 to 80 ka in the Empty Quarter has important implications for hypotheses concerning the timing and routes of dispersal of Homo sapiens out of Africa, which have been much debated. Consequently, the data presented here fill a crucial gap in palaeoenvironmental and archaeological understanding of the southern Arabian interior. Fossils of H. sapiens in the Levant, also dated to MIS 5, together with Middle Palaeolithic archaeological sites in Arabia and India are thought to represent the earliest dispersal of our species out of Africa. We suggest that the widespread occurrence of similar lithic technologies across southern Asia, coupled with a growing body of evidence for environmental amelioration across the Saharo-Arabian belt, indicates that occupation of the Levant by H. sapiens during MIS 5 may not have been a brief, localized ‘failed dispersal’, but part of a wider demographic expansion.