Land use change is one of the major factors that affect soil organic carbon (SOC) variation and global carbon balance. However, the effects of land use change on SOC are always variable. In this study, using a series of paired-field experiments, we estimated the effects of revegetation types and environmental conditions on SOC stock and vertical distribution after replacement of cropland with poplar (Populus tomentosa) and korshinsk peashrub (Caragana korshinskii) in three climate regions (Chifeng City, Fengning City and Datong City of the ′Beijing-Tianjin Sandstorm Source Control′ (BTSSC) program area. The results show that SOC sequestration rate ranges from 0.15 Mg/(ha·yr) to 3.76 Mg/(ha·yr) in the soil layer of 0–100 cm in early stage after cropland afforestation in the BTSSC program area. The SOC accumulation rates are the highest in Fengning for both the two vegetation types. Compared to C. korshinskii, P. tomentosa has greater effects on SOC accumulation in the three climate regions, but significantly greater effect only appears in Datong. The SOC density increases by 20%–111% and 15%–59% for P. tomentosa and 9%–63% and 0–73% for C. korshinskii in the 0–20 cm and 20–100 cm soil layers, respectively. Our results indicate that cropland afforestation not only affects SOC stock in the topsoil, but also has some effects on subsoil carbon. However, the effect of cropland afforestation on SOC accumulation varied with climate regions and revegetation types. Considering the large area of revegetation and relatively high SOC accumulation rate, SOC sequestration in the BTSSC program should contribute significantly to decrease the CO2 concentration in the atmosphere.