The evolutionary success of humans can be attributed to our ability to adapt to ever-changing environments. This reproductive and adaptive success is demonstrated by the 7 billion living humans, occupying nearly every corner of the globe. However, the expansion of humans is an evolutionarily recent development; fossil, genetic and archaeological evidence indicates that humans and our hominin ancestors frequently failed to adapt to climatic fluctuations, leading to demographic contractions and regional extinctions. Remarkably little is known about the history of these evolutionary successes and failures across vast regions of the world, including in the Arabian Desert - a critical biogeographical landbridge for hominins and other animals. Although poorly known, the Arabian Desert preserves spectacular Pleistocene and Holocene records, with considerable potential for elucidating evolutionary patterns and processes on a variety of spatial and temporal scales. The PALAEODESERTS project sets forth a series of testable hypotheses to address the relations between humid and arid climatic periods and population expansions, contractions and extinctions. To address the hypotheses a bold interdisciplinary approach is taken, combining information from palaeoenvironmental studies, palaeontology, geography, geochronology, animal and human genetics, archaeology, rock art studies and linguistics. Examination of hominin and animal population histories provides a comparative framework to assess when, why and how novel cultural behaviours provided survival benefits to hominins. The PALAEODESERTS project will have a profound effect on our understanding of Arabia’s place in the story of human evolution and, more broadly, on the relationship between environmental change, population history, and cultural innovations. This project is uniquely placed to understand our past and contextualise the present at a time when climate change is of considerable public and academic interest and concern.