Cattle pastoralism is an important trait of African cultures. Ethnographic studies describe the central role played by domestic cattle within many societies, highlighting its social and ideological value well beyond its mere function as ‘walking larder’. Historical depth of this African legacy has been repeatedly assessed in an archaeological perspective, mostly emphasizing a continental vision. Nevertheless, in-depth site-specific studies, with a few exceptions, are lacking. Despite the long tradition of a multi-disciplinary approach to the analysis of pastoral systems in Africa, rarely do early and middle Holocene archaeological contexts feature in the same area the combination of settlement, ceremonial and rock art features so as to be multi-dimensionally explored: the Messak plateau in the Libyan central Sahara represents an outstanding exception. Known for its rich Pleistocene occupation and abundant Holocene rock art, the region, through our research, has also shown to preserve the material evidence of a complex ritual dated to the Middle Pastoral (6080–5120 BP or 5200–3800 BC). This was centred on the frequent deposition in stone monuments of disarticulated animal remains, mostly cattle. Animal burials are known also from other African contexts, but regional extent of the phenomenon, state of preservation of monuments, and associated rock art make the Messak case unique. GIS analysis, excavation data, radiocarbon dating, zooarchaeological and isotopic (Sr, C, O) analyses of animal remains, and botanical information are used to explore this highly formalized ritual and the lifeways of a pastoral community in the Holocene Sahara.