Soils have the capacity to store three times more carbon (C) than the atmosphere. This fact has focused scientific and governmental attention because it is one way to mitigate climate change. However, there comes a time when the capacity of soils to store C reaches a limit, considering soil organic carbon (SOC) saturation. In the Mediterranean area, agricultural soils are traditionally exposed to conventional tillage (CT), causing soil properties and quality degradation. Therefore, this study aimed to determine whether CT modifies the carbon storage capacity (carbon saturation), linked to soil mineral fractions <20 µm in olive grove soil in a Mediterranean area over 15 years. The results showed losses of SOC and soil organic carbon stock (SOC-S) over the period studied. Moreover, CT significantly affected aggregate grain size, reducing the percentage of small macro-aggregates (2000–250 µm) by 51.1%, 32.9%, 46.6%, and 50.6% for the Ap, Bw, BC, and C horizons, respectively, and promoting an increase in fine fractions (large micro-aggregates (250–53 µm), silt + clay fraction (53–20 µm) and fine silt + clay (<20 µm)). After 15 years, SOC fractionation showed a decrease in SOC concentration within the large macro-aggregate fraction (>2000 µm) of 38.6% in the Bw horizon; however, in the small macro-aggregates (2000–250 µm), an increase in SOC concentration over time, of 33.5%, was observed in the Ap and Bw horizons. This increasing trend continued in the fine soil fractions. Concerning SOC bound to the fine mineral fraction (<20 µm), evolution over time with CT led to an increase in soil sequestration capacity in the first horizons of 44.7% (Ap horizon) and 42.9% (Bw horizon), and a decrease in depth (BC horizon) of 31.3%. Finally, the total saturated soil organic carbon stock (T-SOC-Ssat), after 15 years, experienced an increase of 30.5 Mg ha−1, and these results conditioned the soil organic carbon stock deficit (SOC-Sdef), causing a potential increase in the capacity of soils to sequester carbon, of 15.2 Mg ha−1 in 15 years. With these results, we can affirm that the effect of CT in the medium term has conditioned the degradation of these soils and the low SOC concentrations, and has therefore made it possible for these soils, with the application of sustainable management practices, to have a high carbon storage capacity and become carbon sinks.