While studies have shown that mammalian herbivores often limit aboveground carbon storage in savannas, their effects on belowground soil carbon storage remains unclear. Using three sets of long-term, large herbivore exclosures with paired controls, we asked how almost two decades of herbivore removal from a semi-arid savanna in Laikipia, Kenya affected aboveground (woody and grass) and belowground soil carbon sequestration, and determined the major source (C vs. C ) of belowground carbon sequestered in soils with and without herbivores present. Large herbivore exclusion, which included a diverse community of grazers, browsers, and mixed-feeding ungulates, resulted in significant increases in grass cover (~22%), woody basal area (~8 m ha ) and woody canopy cover (31%), translating to a ~8.5 t ha increase in aboveground carbon over two decades. Herbivore exclusion also led to a 54% increase (20.5 t ha ) in total soil carbon to 30 cm depth, with ~71% of this derived from C grasses (vs. ~76% with herbivores present) despite substantial increases in woody cover. We attribute this continued high contribution of C grasses to soil C sequestration to the reduced offtake of grass biomass with herbivore exclusion together with the facilitative influence of open sparse woody canopies (e.g. Acacia spp.) on grass cover and productivity in this semi-arid system.