As climate change continues to threaten human and natural systems, the search for cost-effective and practical mitigation solutions is gaining momentum. Reforestation has recently been identified as a promising nature-based climate solution. Yet there are context-dependent biophysical, financial, land-use and operational constraints to reforestation that demand careful consideration. Here, we show that 121 million ha of presently degraded land in Southeast Asia, a region noted for its significant reforestation potential, are biophysically suitable for reforestation. Reforestation of this land would contribute 3.43 ± 1.29 PgCO2e yr−1 to climate mitigation through 2030. However, by taking a combination of on-the-ground financial, land use and operational constraints into account, we find that only a fraction of that mitigation potential may be achievable (0.3–18%). Such constraints are not insurmountable, but they show that careful planning and consideration are needed for effective landscape-scale reforestation.