The first complex, highly organised, state-level societies emerged in the Afro-Asiatic monsoon belt and northern South America during the 6th and early 5th millennia BP. This was a period of profound climatic and environmental change in these regions and globally, characterised by a weakening of the global monsoon system and widespread aridification in regions that today contain the bulk of the world's warm deserts. This paper examines trajectories of socio-cultural and environmental change in six key regions in which complex societies emerged during the Middle Holocene: the central Sahara (focusing on the Libyan Fezzan), Egypt, Mesopotamia, South Asia (Indus–Sarasvati region), northern China and coastal Peru. Links between environmental and socio-cultural change are explored in the context of archaeological and palaeoenvironmental data and a theoretical framework of increasing social complexity as a response to enhanced aridity, driven largely by population agglomeration in environmental refugia characterised by the presence of surface water. There is direct evidence of adaptation to increased aridity in the archaeological literature relating to the Sahara and Egypt. In the other regions examined, the data are consistent with the notion that increased social complexity was largely driven by environmental deterioration, although further local-scale archaeological and palaeoenvironmental data are required to clarify the processes involved.