Arabia is a key area for the dispersal of anatomically modern humans (AMH, Homo sapiens) out of Africa. Given its modern hostile environment, the question of the timing of dispersal is also a question of climatic conditions. Fresh water and food were crucial factors facilitating AMH expansions into Arabia. By dating relict lake deposits, four periods of lake formation were identified: one during the early Holocene and three during the late Pleistocene centered ca. 80, ca. 100, and ca. 125 ka. Favorable environmental conditions during these periods allowed AMH to migrate across southern Arabia. Between ca. 75 and 10.5 ka, arid conditions prevailed and turned southern Arabia into a natural barrier for human dispersal. Thus, expansion of AMH through the southern corridor into Asia must have taken place before 75 ka, possibly in multiple dispersals.