Despite global commitments to forest restoration, evidence of the pathways through which restoration creates social and ecological benefits remains limited. The objective of this paper is to provide empirical evidence to generate insights on the relationship between forest cover change and key provisioning ecosystem services and reforestation pathways. In Southern Ethiopia, three zones along a gradient of decreasing land cover complexity and tree cover were examined. The land cover change was assessed using satellite remote sensing and complemented ground-based tree inventory. Perceptions of land cover and ecosystem services change and farmer responses were evaluated through three Participatory Rural Appraisals and eight Focus Group Discussions. Since the 1970s, a landscape shift from a forested grassland to a cropland mosaic was associated with increased food production, improved food security, and higher incomes. However, this shift also coincided with reductions in livestock, construction materials, fuelwood and water availability, prompting reforestation efforts designed to recover some of these lost ecosystem services. In particular, some households established Eucalyptus woodlots and encouraged natural regeneration. Natural trees, Eucalyptus woodlots, Ensete plantations (a type of plantain), and grasslands were positively associated with homestead proximity; thus, homestead establishment resulting from population increase in this predominately agricultural landscape appeared to foster a viable forest restoration pathway—that is, ‘more people, more trees’. This is a reforestation pathway not previously described in the literature. A return to a more diverse agricultural landscape mosaic provided more secure and diversified income sources along with better provisioning of construction materials, fuelwood, and higher livestock numbers.