Background/Question/Methods Grazing ecosystems occupy more than one-third of the world’s terrestrial realm, and large mammalian herbivores exert strong influence over global biogeochemical cycles. Despite herbivores diverting a major fraction of plant production away from towards secondary production, grazing ecosystems feature carbon rich soils. Paradoxically, compared to no grazing at all moderate grazing promotes soil-C storage. A potential explanation could involve indirect effects where grazing extends the residence time of carbon in soil. In other words, a smaller quantity of C-input enters the soil pool but decomposes slowly under grazing, compared to larger quantities which decompose rapidly in the absence of grazing. The question now becomes what can explain such an effective difference in residence time of carbon in soil. One promising explanation, is through grazer-mediated effects on soil microbial extracellular enzymes. We used a replicated long-term herbivore-exclusion experiment to measure grazer-effects on above- and below-ground plant biomass, soil-C stock, different soil-C pools, microbial biomass, and three enzymes relevant to the C-cycle: peroxidase – which acts on recalcitrant matter such as lignin, and beta-glucosidase and cellobiohydrolase – which act on more labile fractions. We hypothesise that grazing induced shifts in recalcitrant-C modifying peroxidase can regulate soil-C storage, and any parallel response in glucosidase and cellobiohydrolase should be unrelated to soil-C storage. Results/Conclusions Consistent with the paradox, 12 years of herbivore-exclusion did not result in higher soil-C in the fenced plots despite 50–80% higher plant biomass than the grazed plots. Instead we find soil-C stock to not change with grazing. Grazing-exclusion increased recalcitrant and intermediate soil-C, and decrease labile-C. Grazer-effects on peroxidase was inversely related with that in soil-C. But changes in beta-glucosidase, and cellobiohydrolase were unrelated to changes in soil-C. We also find grazing-exclusion to increase microbial respiration. This could explain why even though grazing-exclusion increases recalcitrant-C, soil-C stock remains unchanged. Path-analysis with structural equation models supported the hypothesis that grazing influences soil-C via its indirect effects on soil microbial functions and reduces peroxidase activity to favor net soil-C storage. High spatial variability in these grazer-effects captured by mixed-effects models suggest that they can be stronger in dry than in mesic ecosystems. This establishes linkages between herbivores and decomposers that may be consequential for understanding and managing ecosystem functions and services, particularly in drylands supporting large-mammalian herbivores.