The Jebel Ousselat, on the eastern edge of the Atlas Mountains in Tunisia, is a semi-arid, degraded uplandlandscape; in many ways, it is a marginal environment. Here we present evidence from the early to middleHolocene (ca. 6200–4200 bc), a period of significant climate change in the wider region, moving fromthe African Humid Period towards an arid environment and the development to the south of the Saharandesert. Employing rock art and lithic evidence from across the landscape, we consider how these strands ofarchaeological evidence intersect and facilitate the description of human–environment interactions thatwere wholly different from those we see today. The interpretation of the full range of sites is underpinnedby a landscape/environmental framework that considers site location and relationships with topographyand hydrology. We also develop a socio-ecological approach that avoids environmental determinism butwillingly accepts the role that the environment plays in contributing to the structure of human activityin a complex landscape. The art and archaeology of the Jebel Ousselat reflect complex interactions duringa period of environmental, economic and cultural change. We feel that the art is not a mere reflection offood procurement but instead points to the production of complex socio-ecological relationships during aperiod of transition.