Removing carbon dioxide (CO2) from the atmosphere and storing the carbon (C) in resistant soil organic matter (SOM) is a global priority to restore soil fertility and help mitigate climate change. Although it is widely assumed that retaining rather than removing or burning crop residues will increase SOM levels, many studies have failed to demonstrate this. We hypothesised that the microbial nature of resistant SOM provides a predictable nutrient stoichiometry (C:nitrogen, C:phosphorus and C:sulphur-C:N:P:S) to target using supplementary nutrients when incorporating C-rich crop residues into soil. An improvement in the humification efficiency of the soil microbiome as a whole, and thereby C-sequestration, was predicted. In a field study over 5 years, soil organic-C (SOC) stocks to 1.6 m soil depth were increased by 5.5 t C ha-1 where supplementary nutrients were applied with incorporated crop residues, but were reduced by 3.2 t C ha-1 without nutrient addition, with 2.9 t C ha-1 being lost from the 0-10 cm layer. A net difference of 8.7 t C ha-1 was thus achieved in a cropping soil over a 5 year period, despite the same level of C addition. Despite shallow incorporation (0.15 m), more than 50% of the SOC increase occurred below 0.3 m, and as predicted by the stoichiometry, increases in resistant SOC were accompanied by increases in soil NPS at all depths. Interestingly the C:N, C:P and C:S ratios decreased significantly with depth possibly as a consequence of differences in fungi to bacteria ratio. Our results demonstrate that irrespective of the C-input, it is essential to balance the nutrient stoichiometry of added C to better match that of resistant SOM to increase SOC sequestration. This has implications for global practices and policies aimed at increasing SOC sequestration and specifically highlight the need to consider the hidden cost and availability of associated nutrients in building soil-C.