Long-term cultivation of steppe soils in a nonsustainable way caused severe soil degradation and reduced agricultural productivity in Eastern Europe, one of the world's most important areas for cereal production. In order to combat soil erosion and maintain yields, a widespread system of tree windbreaks was introduced in the 1950s, accompanied by improved agricultural practices in recent years. However, information on the effectiveness of such measures to rebuild soil organic carbon (SOC) is scarce. The objective of this study was to estimate the OC storage potential of the fine mineral fraction of degraded arable steppe soils in Moldova and to quantify SOC sequestration rates under (a) windbreaks, (b) cropland with improved crop rotation/manure application, and (c) cropland with cover cropping. Natural grassland relicts served as a reference to estimate the SOC saturation potential. Our results revealed a low SOC saturation of 50% under conventional agricultural use due to high SOC losses, indicating a high potential for SOC sequestration. Relatively high SOC sequestration rates were determined for topsoils (0–30 cm) under windbreaks (0.9 t ha⁻¹ yr⁻¹), improved crop rotation/manure application (1.3 t ha⁻¹ yr⁻¹), and cover cropping (1.9 t ha⁻¹ yr⁻¹). In this regard, sequestration rates derived from OC changes of the fine fraction may be more reliable than total SOC-based rates, particularly for windbreaks with high proportions of labile SOC. We conclude that implementation of improved agricultural management together with the maintenance of windbreaks is a promising strategy to rebuild SOC, reduce widespread soil erosion and compaction, and secure Moldova's agricultural productivity.