There is widespread empirical evidence that protist grazing on bacteria reduces bacterial abundances but increases bacteria-mediated decomposition of organic matter. This paradox has been noted repeatedly in the microbiology literature but lacks a generally accepted mechanistic explanation. To explain this paradox quantitatively, we develop a bacteria-grazer model of organic matter decomposition that incorporates protozoa-driven nutrient recycling and stoichiometry. Unlike previous efforts, the current model includes explicit limitation, via Liebig’s law of minimum, by two possible factors, nutrient and carbon densities, as well as their relative ratios in bacteria and grazers. Our model shows two principal results: (1) when the environment is carbon limiting, organic matter can always be decomposed completely, regardless of the presence/absence of grazers; (2) when the environment is nutrient (such as nitrogen) limiting, it is possible for organic matter to be completely decomposed in the presence, but not absence, of grazers. Grazers facilitate decomposition by releasing nutrients back into the environment, which would otherwise be limiting, while preying upon bacteria. Model analysis reveals that facilitation of organic matter decomposition by grazers is positively related to the stoichiometric difference between bacteria and grazers. In addition, we predict the existence of an optimal density range of introduced grazers, which maximally facilitate the decomposition of organic matter in a fixed time period. This optimal range reflects a trade-off between grazer-induced nutrient recycling and grazer-induced mortality of bacteria.