The Loess Plateau of China has the highest soil erosion rate in the world where billion tons of soil is annually washed into Yellow River. In recent decades this region has experienced significant climate change and policy-driven land conversion. However, it has not yet been well investigated how these changes in climate and land use have affected soil organic carbon (SOC) storage on the Loess Plateau. By using the Dynamic Land Ecosystem Model (DLEM), we quantified the effects of climate and land use on SOC storage on the Loess Plateau in the context of multiple environmental factors during the period of 1961–2005. Our results show that SOC storage increased by 0.27 Pg C on the Loess Plateau as a result of multiple environmental factors during the study period. About 55% (0.14 Pg C) of the SOC increase was caused by land conversion from cropland to grassland/forest owing to the government efforts to reduce soil erosion and improve the ecological conditions in the region. Historical climate change reduced SOC by 0.05 Pg C (approximately 19% of the total change) primarily due to a significant climate warming and a slight reduction in precipitation. Our results imply that the implementation of “Grain for Green” policy may effectively enhance regional soil carbon storage and hence starve off further soil erosion on the Loess Plateau.