Dated archaeological sites are absent in northern Arabia between the Last Glacial Maximum (LGM) and 10,000 years ago (ka), signifying potential population abandonment prior to the onset of the Holocene humid period. Here we present evidence that playas became established in the Nefud desert of northern Arabia between ~16 and ~13 ka, the earliest reported presence of surface water following the hyper-aridity of the LGM. These fresh water sources facilitated human expansions into arid landscapes as shown by new excavations of stratified archaeological sites dating to between 12.8 and 11.4 ka. During the Pleistocene-Holocene transition, human populations exploited a network of seasonal water bodies - marking locations and access routes with monumental rock engravings of camels, ibex, wild equids, gazelles, and aurochs. These communities made distinctive stone tool types showing ongoing connections to the late Epipalaeolithic and Pre-Pottery Neolithic populations of the Levant.