With anthropogenic nutrient inputs to ecosystems increasing globally, there are long-standing, fundamental questions about the role of nutrients in the decomposition of organic matter. We tested the effects of exogenous nitrogen and phosphorus inputs on litter decomposition across a broad suite of litter and soil types. In one experiment, C mineralization was compared across a wide array of plants individually added to a single soil, while in the second, C mineralization from a single substrate was compared across 50 soils. Counter to basic stoichiometric decomposition theory, low N availability can increase litter decomposition as microbes use labile substrates to acquire N from recalcitrant organic matter. This "microbial nitrogen mining" is consistently suppressed by high soil N supply or substrate N concentrations. There is no evidence for phosphorus mining as P fertilization increases short- and long-term mineralization. These results suggest that basic stoichiometric decomposition theory needs to be revised and ecosystem models restructured accordingly in order to predict ecosystem carbon storage responses to anthropogenic changes in nutrient availability.