The Nationally Determined Contributions (NDCs) of several non-Annex I countries mention agroforestry but mostly without associated mitigation target. The absence of reliable data, including on existing agroforestry practices and their carbon storage, partially constrains the target setting. In this paper, we estimate the mitigation potential of agroforestry carbon sequestration in Vietnam using a nationwide agroforestry database and carbon data from the literature. Sequestered carbon was estimated for existing agroforestry systems and for areas into which these systems can be expanded. Existing agroforestry systems in Vietnam cover over 0.83 million hectares storing a 1346 ± 92 million ton CO2 equivalent including above-, belowground, and soil carbon. These systems could be expanded to an area of 0.93–2.4 million hectares. Of this expansion area, about 10% is considered highly suitable for production, with a carbon sequestration potential of 2.3–44 million ton CO2 equivalent over the period 2021–2030. If neglecting agroforestry’s potential for modifying micro-climates, climate change can reduce the highly suitable area of agroforestry and associated carbon by 34–48% in 2050. Agroforestry can greatly contribute to Vietnam’s 2021–2030 NDC, for example, to offset the greenhouse gas emissions of the agriculture sector.