Climate warming at high northern latitudes has caused substantial increases in plant productivity of tundra vegetation and an expansion of the range of deciduous shrub species. However significant the increase in carbon (C) contained within above-ground shrub biomass, it is modest in comparison with the amount of C stored in the soil in tundra ecosystems. Here, we use a ‘space-for-time’ approach to test the hypothesis that a shift from lower-productivity tundra heath to higher-productivity deciduous shrub vegetation in the sub-Arctic may lead to a loss of soil C that out-weighs the increase in above-ground shrub biomass. We further hypothesize that a shift from ericoid to ectomycorrhizal systems coincident with this vegetation change provides a mechanism for the loss of soil C. We sampled soil C stocks, soil surface CO2 flux rates and fungal growth rates along replicated natural transitions from birch forest (Betula pubescens), through deciduous shrub tundra (Betula nana) to tundra heaths (Empetrum nigrum) near Abisko, Swedish Lapland. We demonstrate that organic horizon soil organic C (SOCorg) is significantly lower at shrub (2.98 ± 0.48 kg m−2) and forest (2.04 ± 0.25 kg m−2) plots than at heath plots (7.03 ± 0.79 kg m−2). Shrub vegetation had the highest respiration rates, suggesting that despite higher rates of C assimilation, C turnover was also very high and less C is sequestered in the ecosystem. Growth rates of fungal hyphae increased across the transition from heath to shrub, suggesting that the action of ectomycorrhizal symbionts in the scavenging of organically bound nutrients is an important pathway by which soil C is made available to microbial degradation. The expansion of deciduous shrubs onto potentially vulnerable arctic soils with large stores of C could therefore represent a significant positive feedback to the climate system.