Forest restoration is gaining momentum as a natural climate solution to provide carbon dioxide removal while also addressing the biodiversity crisis. Globally, three primary restoration strategies—natural regeneration, assisted natural regeneration, and active restoration—have been adopted. However, inconsistent monitoring of forest dynamics mean large uncertainties remain over their long-term potential to enhance carbon (C) removal. We examined over 30 years of forest aboveground carbon (AGC) estimates from high-resolution lidar, Landsat imagery, and field data across East Africa. Our study shows that assisted natural regeneration and active restoration outperform natural regeneration in enhancing forest C removal capacity, with long-term implementation (over 9 years) needed to overcome the initial lags in AGC accumulation. Restoring 14.24 million hectares of suitable areas available in East Africa, representing 2.1% of suitable restoration areas globally, could enhance forest C removal by 2.85 ± 0.82 gigatons of C (Gt C) by 2050. However, less than one quarter of this potential would be achieved by 2030. This research advances our understanding of forest restoration’s potential for enhancing C removal and the time scale for meeting climate targets. We demonstrate that long-term commitments in implementation and investment are critical for restoring forests effectively for climate mitigation.