Fire frequency is changing globally and is projected to affect the global carbon cycle and climate. However, uncertainty about how ecosystems respond to decadal changes in fire frequency makes it difficult to predict the effects of altered fire regimes on the carbon cycle; for instance, we do not fully understand the long-term effects of fire on soil carbon and nutrient storage, or whether fire-driven nutrient losses limit plant productivity. Here we analyse data from 48 sites in savanna grasslands, broadleaf forests and needleleaf forests spanning up to 65 years, during which time the frequency of fires was altered at each site. We find that frequently burned plots experienced a decline in surface soil carbon and nitrogen that was non-saturating through time, having 36 per cent (±13 per cent) less carbon and 38 per cent (±16 per cent) less nitrogen after 64 years than plots that were protected from fire. Fire-driven carbon and nitrogen losses were substantial in savanna grasslands and broadleaf forests, but not in temperate and boreal needleleaf forests. We also observe comparable soil carbon and nitrogen losses in an independent field dataset and in dynamic model simulations of global vegetation. The model study predicts that the long-term losses of soil nitrogen that result from more frequent burning may in turn decrease the carbon that is sequestered by net primary productivity by about 20 per cent of the total carbon that is emitted from burning biomass over the same period. Furthermore, we estimate that the effects of changes in fire frequency on ecosystem carbon storage may be 30 per cent too low if they do not include multidecadal changes in soil carbon, especially in drier savanna grasslands. Future changes in fire frequency may shift ecosystem carbon storage by changing soil carbon pools and nitrogen limitations on plant growth, altering the carbon sink capacity of frequently burning savanna grasslands and broadleaf forests.