Achieving food security through intensive agricultural practices on low fertility soils is challenging as crop productivity is increasingly curtailed by the loss of soil structural stability and rapid depletion of soil organic carbon (SOC). As such, the conversion from traditional mono-cropping to legume-cereal intercropping, especially with integrated fertilization, may increase crop yields with the least ecological footprint. We set up a 2-year field experiment in a split-plot design with cowpea-maize monoculture and intercropping under different organic–inorganic fertilization regimes, including no fertilization (control), organic input only (compost), chemical input only (NPK), and multi-nutrient enriched compost (NPKEC). We observed that intercropped maize had a significantly higher biomass yield compared to the corresponding monoculture when fertilized with NPKEC fertilizer. However, cowpea biomass yield differences between monoculture and intercropped plots were comparable under all fertilization regimes. In contrast, the grain yield advantage of both maize and cowpea was significantly enhanced under the intercropping system compared to monoculture, with NPKEC showing the most significant effect among all fertilization regimes. When comparing the relative contribution of the fertilization regime to SOC, the NPKEC fertilizer provided the highest SOC-sequestration (0.30 Mg C/ha yr). At the same time, the effect of the cropping system on C-sequestration showed that intercropping provided the highest C-sequestration (0.17 Mg C/ha yr) compared to monocultures of both crops. Although compost application significantly increased mineral associated (MAOC) and particulate associated organic carbon (PAOC) concentrations compared to unfertilized control plots, NPKEC fertilization with intercropping system was the most effective combination causing the greatest increase of both soil C pools over time. Based on redundancy analysis (RDA), the positive association of MAOC and PAOC with C-sequestration suggests the importance of both organic fractions as primary C reservoirs conducting SOC storage. Importantly, although compost alone in association with intercropping had a lower C-sequestration, it was associated to a better soil structure as confirmed by its positive relationship with macro-and micro-aggregation, water stable aggregates (WSA), and mean weight diameter (MDA). Overall, our results indicate the importance of restoring soil structure in degraded soils through appropriate land management solutions, such as stoichiometrically balanced fertilization practices (NPKEC) and crop diversification (intercropping), in order to achieve significant gains in SOC storage and, ultimately, improve crop productivity.