Large herbivores can control plant community composition and, under certain conditions, even induce vegetation shifts to alternative ecosystem states. As different plant assemblages maintain contrasting carbon (C) cycling patterns, herbivores have the potential to alter C sequestration at regional scales. Their influence is of particular interest in the Arctic tundra, where a large share of the world's soil C reservoir is stored. We assessed the influence of grazing mammals on tundra vegetation and C stocks by resampling two sites located along pasture rotation fences in northern Norway. These fences have separated lightly grazed areas from heavily grazed areas (in close proximity to the fences) and moderately grazed areas (further away from the fences) for the past 50 years. Fourteen years earlier, the lightly and moderately grazed areas were dominated by dwarf shrubs, whereas heavy grazing had promoted the establishment of graminoid-dominated vegetation. Since then, both reindeer densities and temperatures have increased, and more time has passed for transient dynamics to be expressed. We expected that the vegetation and C stocks would have changed under all grazing intensities, but not necessarily in the same way. At the site where relative reindeer numbers and trampling intensity had increased the most, graminoid-dominated vegetation was now also found in the moderately grazed area. At the other site, the dominant vegetation types under all grazing intensities were the same as 14 years earlier. We show that the heavily grazed, graminoid-dominated areas stored less C above-ground than the lightly grazed, shrub-dominated areas. Yet, the below-ground consequences of grazing-induced grassification varied between the sites: Grazing did not alter organic soil C stocks at the site where both evergreen and deciduous shrubs were abundant in the lightly grazed area, whereas heavy grazing increased organic soil C stocks at the site where the deciduous shrub Betula nana was dominant. Our results indicate that, despite the negative impacts of grazers on above-ground C storage, their impact on below-ground C may even be positive. We suggest that the site-specific responses of organic soil C stocks to grazing could be explained by the differences in vegetation under light grazing. This would imply that the replacement of deciduous shrubs by graminoids, as a consequence of grazing could be beneficial for C sequestration in tundra soils. A plain language summary is available for this article.