Frequent fire and grazing by megafauna are important determinants of tallgrass prairie plant community structure. However, fire suppression and removal of native grazers have altered these natural disturbance regimes and changed grassland plant communities with potential long‐term consequences for soil carbon (C) and nitrogen (N) storage. We investigated multi‐decade changes in soil C and N pools in response to contrasting long‐term burning and grazing treatments. Fire suppression with or without grazers, and exclusion of grazers in annually‐burned prairie increased soil C content and shifted the δ13C signature of soil C over time, concomitant with changes in plant community composition. Soil δ13C values indicated that increased soil C content was associated with an increased contribution from plants using a C3 photosynthetic pathway (i.e., woody shrubs) under fire suppression. Soil N content also increased when fire was suppressed, relative to frequently burned grassland, but the rate of increase was slower when grazers were present. Additionally, changes in δ15N values suggested that grazing increased the openness of the N cycle, presumably due to greater N losses. By coupling long‐term fire and grazing treatments with plant community data and soil samples archived over three decades, we demonstrate that human‐caused changes to natural disturbance regimes in a tallgrass prairie significantly alters soil C and N cycles through belowground changes associated with shifts in the plant community. Since natural disturbance regimes have been altered in grasslands across the world, our results are relevant for understanding the long‐term biogeochemical consequences of these ongoing land‐use changes.