Mediterranean Africa forms a crucial junction between the wider Saharan zone and the rest of the Mediterranean. In contrast to its well-investigated history from the first millennium BC onward, its antecedent dynamics are very poorly understood, and deeper archaeological histories of the Mediterranean therefore remain unbalanced and incomplete. This paper draws on a new surge in data to present the first up-todate interpretative synthesis of this region’s archaeology from the start of the Holocene until the threshold of the Iron Age (9600–1000 bc). It presents the evidence for climatic, environmental and sea-level change, followed by analysis of the chronological and spatial patterning of all radiocarbon dates from Mediterranean Africa, brought together for the first time. The principal exploration then divides into three phases. During Phase 1 (9600–6200 bc) diverse forms of hunting, gathering and foraging were ubiquitous. Phase 2 (6200–4000 bc) witnessed more continuity than elsewhere in the Mediterranean, but also the widespread uptake of domesticated livestock and gradual evolution of herding societies, as well as limited enclaves of farming. Phase 3 (4000–1000 bc) has been least explored, outside developments in Egypt; in the east this phase witnessed the emergence of fully nomadic and transhumant pastoralism, with political superstructures, while trajectories in the west remain obscure, but in parts of the Maghreb suggest complex possibilities. Contacts with the Mediterranean maritime world grew during the third and second millennia bc, while interaction to the south was transformed by desertification. Understanding how the southern Mediterranean shore was drawn into Iron Age networks will require much better knowledge of its indigenous societies. The present constitutes a pivotal moment, in terms of accumulated knowledge, pathways for future investigation and engagement with a challenging current geopolitical situation.