The Arabian Peninsula is a key region for understanding climate change and human occupation history in a marginal environment. The Mundafan palaeolake is situated in southern Saudi Arabia, in the Rub' al-Khali (the 'Empty Quarter'), the world's largest sand desert. Here we report the first discoveries of Middle Palaeolithic and Neolithic archaeological sites in association with the palaeolake. We associate the human occupations with new geochronological data, and suggest the archaeological sites date to the wet periods of Marine Isotope Stage 5 and the Early Holocene. The archaeological sites indicate that humans repeatedly penetrated the ameliorated environments of the Rub' al-Khali. The sites probably represent short-term occupations, with the Neolithic sites focused on hunting, as indicated by points and weaponry. Middle Palaeolithic assemblages at Mundafan support a lacustrine adaptive focus in Arabia. Provenancing of obsidian artifacts indicates that Neolithic groups at Mundafan had a wide wandering range, with transport of artifacts from distant sources.