Vegetation restoration is one of the most important measures to improve accumulation and storage of soil organic carbon (SOC). The objective of our study was to understand the response of soil organic carbon to vegetation restoration in different erosion environments in the hilly-gullied region of the Loess Plateau. The study was thus conducted on 42 restored slopes and six sloping croplands (control) in the Fangta watershed and the Manhonggou watershed, which are located, respectively, in the Loess area and Sandstone area and is characterized by different erosion environments. Variations in soil organic carbon content (SOCC) and soil organic carbon density (SOCD) among different plant communities in each erosion environment and among different erosion environments for each plant community were analyzed. In each erosion environment, compared with sloping croplands, SOCC and SOCD decreased significantly at the preliminary stage of natural restoration while the increased significantly with the process of restoration (P < 0.05); and significant increases of SOCC and SOCD were also observed for Caragana korshinskii communities (20-25 a) and Robinia pseudoacacia communities (13-14 a). This shows that soil organic carbon could be improved using both natural and artificial means of restoration within each erosion environment. SOCC and SOCD of R. pseudoacacia communities were much higher than those of Stipa bungeana +Artemisia gmelinii communities (15 a) within each erosion environment (P < 0.05); SOCC and SOCD in C. korshinskii communities (20-25 a) were much lower than in A. gmelinii communities (30 a) in the Sandstone area (P < 0.05); and C. korshinskii communities (20-25 a) had much lower SOCC and much higher SOCD than A. gmelinii communities (30 a) in Loess area (P < 0.05). These results indicate that within the same duration of restoration, compared with natural restoration, R. pseudoacacia afforestation could accumulate and store more SOC within each erosion environment. The effectiveness of C. korshinskii afforestation for accumulating SOC was not superior within all erosion environments, however, its effectiveness in storing SOC was superior in the Loess area but not in the Sandstone area. Both artificial and natural communities had higher SOCC in the Loess area than in Sandstone area, and artificial and natural communities had higher SOCD and lower SOCD in the Loess area than in the Sandstone area, respectively. Therefore, in contrast to the Sandstone area, artificial restoration in the Loess area was more effective at accumulating and storing SOC, and natural restoration was superior in accumulating SOC, but not in storing SOC.