Climate-Smart Villages (CSVs) were established by the CGIAR Research Program on Climate Change, Agriculture and Food Security (CCAFS) in the East African countries of Kenya, Tanzania and Uganda to test and promote a portfolio of climate-smart agriculture (CSA) practices that have climate change mitigation potential. This study evaluated the soil carbon sequestration potential of these CSVs compared to the control land use that did not have CSA practices. At the one-meter depth, soil carbon stocks increased by 20–70%, 70–86%, and 51–110% in Kenya, Tanzania and Uganda CSVs, respectively, compared to control. Consequently, CSVs contributed to the reduction of emissions by 87–420 Mg CO2 eq ha−1. In the topsoil (0–15 cm), CSVs sequestered almost twice more soil carbon than the control and subsequently emissions were reduced by 42–158 Mg CO2 eq ha−1 under CSVs. The annual increase in carbon sequestration under CSVs ranged between 1.6 and 6.2 Mg C ha−1 yr−1 and substantially varied between the CSA land use types. The forests sequestered the highest soil carbon (5–6 Mg C ha−1 yr−1), followed by grasslands and croplands. The forest topsoil also had lower bulk density compared to the control. The findings suggest that CSA practices implemented through the CSVs approach contribute to climate change mitigation through soil carbon sequestration.