Yuzhniy Oleniy Ostrov in Karelia, northwest Russia, is one of the largest Early Holocene cemeteries in northern Eurasia, with 177 burials recovered in excavations in the 1930s; originally, more than 400 graves may have been present. A new radiocarbon dating programme, taking into account a correction for freshwater reservoir effects, suggests that the main use of the cemetery spanned only some 100–300 years, centring on ca. 8250 to 8000 cal BP. This coincides remarkably closely with the 8.2 ka cooling event, the most dramatic climatic downturn in the Holocene in the northern hemisphere, inviting an interpretation in terms of human response to a climate-driven environmental change. Rather than suggesting a simple deterministic relationship, we draw on a body of anthropological and archaeological theory to argue that the burial of the dead at this location served to demarcate and negotiate rights of access to a favoured locality with particularly rich and resilient fish and game stocks during a period of regional resource depression. This resulted in increased social stress in human communities that exceeded and subverted the ‘normal’ commitment of many hunter-gatherers to egalitarianism and widespread resource sharing, and gave rise to greater mortuary complexity. However, this seems to have lasted only for the duration of the climate downturn. Our results have implications for understanding the context of the emergence—and dissolution—of socio-economic inequality and territoriality under conditions of socio-ecological stress.