The dispersal of human populations out of Africa into Arabia was most likely linked to episodes of climatic amelioration, when increased monsoon rainfall led to the activation of drainage systems, improved freshwater availability, and the development of regional vegetation. Here we present the first dated terrestrial record from southeast Arabia that provides evidence for increased rainfall and the expansion of vegetation during both glacial and interglacial periods. Findings from extensive alluvial fan deposits indicate that drainage system activation occurred during Marine Isotope Stage (MIS) 6 (ca. 160–150 ka), MIS 5 (ca. 130–75 ka), and during early MIS 3 (ca. 55 ka). The development of active freshwater systems during these periods corresponds with monsoon intensity increases during insolation maxima, suggesting that humid periods in Arabia were not confined to eccentricity-paced deglaciations, and providing paleoenvironmental support for multiple windows of opportunity for dispersal out of Africa during the late Pleistocene.