Food-insecure households in many countries depend on international aid to alleviate acute shocks and chronic shortages. Some food security programmes (including Ethiopia’s Productive Safety Net Program–PSNP – which provides a case study for this article) have integrated aid in exchange for labour on public works to reduce long-term dependence by investing in the productive capacity and resilience of communities. Using this approach, Ethiopia has embarked upon an ambitious national programme of land restoration and sustainable land management. Although the intent was to reduce poverty, here we show that an unintended co-benefit is the climate-change mitigation from reduced greenhouse gas (GHG) emissions and increased landscape carbon stocks. The article first shows that the total reduction in net GHG emissions from PSNP’s land management at the national scale is estimated at 3.4 million Mg CO2e y−1 – approximately 1.5% of the emissions reductions in Ethiopia’s Nationally Determined Contribution for the Paris Agreement. The article then explores some of the opportunities and constraints to scaling up of this impact. Key policy insights Food security programmes (FSPs) can contribute to climate change mitigation by creating a vehicle for investment in land and ecosystem restoration. Maximizing mitigation, while enhancing but not compromising food security, requires that climate projections, and mitigation and adaptation responses should be mainstreamed into planning and implementation of FSPs at all levels. Cross-cutting oversight is required to integrate land restoration, climate policy, food security and disaster risk management into a coherent policy framework. Institutional barriers to optimal implementation should be addressed, such as incentive mechanisms that reward effort rather than results, and lack of centralized monitoring and evaluation of impacts on the physical environment. Project implementation can often be improved by adopting best management practices, such as using productive living livestock barriers where possible, and increasing the integration of agroforestry and non-timber forest products into landscape regeneration.