New data and a review of historiographic information from Neolithic sites of the Malaga and Algarve coasts (southern Iberian Peninsula) and from the Maghreb (North Africa) reveal the existence of a Neolithic settlement at least from 7.5 cal ka BP. The agricultural and pastoralist food producing economy of that population rapidly replaced the coastal economies of the Mesolithic populations. The timing of this population and economic turnover coincided with major changes in the continental and marine ecosystems, including upwelling intensity, sea-level changes and increased aridity in the Sahara and along the Iberian coast. These changes likely impacted the subsistence strategies of the Mesolithic populations along the Iberian seascapes and resulted in abandonments manifested as sedimentary hiatuses in some areas during the Mesolithic–Neolithic transition. The rapid expansion and area of dispersal of the early Neolithic traits suggest the use of marine technology. Different evidences for a Maghrebian origin for the first colonists have been summarized. The recognition of an early North-African Neolithic influence in Southern Iberia and the Maghreb is vital for understanding the appearance and development of the Neolithic in Western Europe. Our review suggests links between climate change, resource allocation, and population turnover.