Archaeological deposits in rock shelters have enormous informative potential, particularly in arid environments where organic materials are well preserved. In these areas, sub-fossilized coprolites and dung remains have been identified as valuable proxies for inferences about past environments, subsistence economies and cultural trajectories. Here we present a multidisciplinary analysis of bovid (ovicaprine) coprolites collected from the Early Holocene hunter-gatherer occupation at Takarkori rock shelter (SW Libya, central Sahara). Our results show that Barbary sheep (Ammotragus lervia) were managed as early as ~9500 years cal BP, mostly with the rearing of juveniles. Palynological analysis of individual pellets suggests a seasonal confinement of the animals and the selection of fodder. GIS analysis of coprolite distribution also indicates sophisticated strategies of Barbary sheep “herding” and spatial differentiation of specialized areas within the rock shelter, including the construction and use of a stone-based enclosure for corralling animals. These highly structured and organized forms of control over wild animals are interpreted as a potential co-evolutionary trigger for the subsequent rapid adoption and integration of the incoming pastoral Neolithic economy.