The storage of soil organic carbon (SOC) in cropland soils is an essential strategy that serves the dual purpose of enhancing soil fertility and mitigating climate change. However, how the stability of stored carbon is altered under long-term fertilization has not been well understood, especially in the double rice cropping system in Chinese paddy soils. In this study, we explored the SOC storage and consequent stability of SOC under long-term fertilization. The soil samples were fractionated chemically to isolate various fractions and constituent pools of SOC (i.e., very labile C/VLC, labile C/LC, less labile C/LLC, and non-labile C/NLC). The following treatments were tested: control (CK), recommended rate of inorganic fertilizer (NPK), double the amount of recommended rate of inorganic fertilizer (2NPK), and NPK combined with manure (NPKM). The results showed that, relative to the initial level, the application of NPKM significantly improved the SOC storage as compared to the control. The long-term NPKM increased the total SOC in the paddy soil and this increased SOC was mainly stored in LLC, as revealed by the highest increase (142%) over the control. Furthermore, the highest proportion of labile pool was associated with unfertilized CK, while the reverse was true for the recalcitrant pool, which was highest under NPKM. This supports the role of combining manure with NPK to improve the stability of SOC, further verified by the high recalcitrance index under NPKM (56.75% for 0–20 cm and 57.69% for 20–40 cm) as compared to the control.