The early Holocene in North Africa remains a poorly known period, documented unequally by region. Eastern Algeria and Tunisia have the greatest number of deposits, but most were excavated decades ago without the controls and recording required for modern interpretation. The chronological framework is based on radiocarbon (14C) dates that are also old, for the most part. Recent work on Mesolithic lithic industries of Western Europe has enabled us to revive the hypothesis of the existence of contacts between the northern and southern shores of the western Mediterranean at least by the 6th millennium cal BC. A collective research program was conducted in 2016–2017 to test this hypothesis with a particular focus on documenting the technological traditions in the lithic industry and situating them precisely in time. We have 46 new radiocarbon dates that were recently carried out on previously excavated Algerian sites, some of which contain several levels, allowing the construction of Bayesian models. These new measures reinforce the hypothesis of contacts between Europe and Africa by demonstrating the contemporaneity of similar technological processes. Above all, they make it possible to accurately refine the chronology of the main cultural entities of the Maghreb at the beginning of the Holocene.