Agricultural activities generate CO2, CH4, and N2O, affecting the global climate and the sustainability of agricultural production systems. This topic is essential in those areas where agriculture has caused soil decarbonization. The soil can regenerate by implementing sustainable soil management (SSM), and this regeneration is finite. Therefore, it is necessary to determine the maximum carbon (C) storage capacity to establish the most SSM for soil recarbonization. This research analyzes the C storage capacity in soils with rainfed olive groves and traditional tillage in the largest olive-oil-producing area in the world (Jaén, Andalusia, Spain). The results show that these soils had low soil organic C (SOC) content, ranging from 5.16 g kg−1 (topsoil) to 1.60 g kg−1 (subsoil) and low SOC stock (SOC-S) (43.12 Mg ha−1; 0–120 cm depth). In addition, the SOC fractionation showed that the highest SOC concentrations were in the particulate organic C form. The SOC-S linked to the fine mineral fraction (<20 µm) in topsoil was 21.93 Mg C ha−1, and the SOC-S saturated ranged between 50.69 and 33.11 Mg C ha−1. Therefore, on the soil surface (0–32.7 cm depth), these soils have a C storage maximum capacity of 28.76 Mg C ha−1, with a net C sink capacity of 105.55 Mg ha−1 of CO2-eq. All this suggests that these soils could have a high recarbonization capacity, and applying SSM (in the coming years) could be an essential C sink.