Socio-ecological systems are complex, dynamic structures driven by cross-scale interactions between climate, disturbance and subsistence strategies. We synthetize paleoecological data to explore the emergence and evolution of anthropogenic landscapes in southwestern Europe and northern Africa. Specifically, we estimate trends in vegetation and fire, and assess how changes in climate and resource exploitation altered ecosystem dynamics over the last 10,000 years. Pollen data reveal that a complex vegetation mosaic resulted from the conversion of forests into areas suitable for crops, especially after 7000 cal yr BP. Cross-scale analysis shows a progressive decoupling of climate and ecosystem trajectories, which displayed an overall south-to-north time-transgressive pattern consistent with models of population expansion. As human impact increased, so did the use of fire, and after 4000 cal yr BP, levels of biomass burning became homogeneous across the region. This region-wide rise in burning suggests that land-management overrode the effects of climate, fuel and topography. Thus, while increasing the returns and predictability of resources, rapidly-growing communities created a new form of frequent and extensive disturbance that led to profound and persistent changes in the landscape, including shrub encroachment, increased erosion and soil impoverishment.