Landscape restoration initiatives are mainly focusing on forest regeneration and agroforestry, especially in the Global South. However, due to a lack of monitoring tools, the carbon balance of restoration efforts remains poorly quantified. Here, we use satellite images from 2008 and 2019 to calculate carbon stocks for individual trees in Rwanda, a country which has been actively engaged in restoration activities over the past decade. We show that smallholder farmers on average planted about 3 trees per farm during 2008–2019, contributing about 50.4 million new trees at the national scale. The overall C sink of the new farmland trees was 0.13 Megagrams of Carbon per hectare per year, which is 6 times lower than gains observed from restoration of degraded forests (0.76 Megagrams of Carbon per hectare per year). If national greenhouse gas emissions remain at the level of 2019, agroforestry (~61% of national area coverage) and continued restoration of degraded natural forests (~0.5% of national area coverage) have the potential to offset about 80% of the national emissions before 2050. Our work monitors and quantifies progress and impact of landscape restoration projects and outlines a pathway to engage smallholder farmers with a limited number of on-farm trees into the expanding carbon market.