Tundra ecosystems are global belowground sinks for atmospheric CO2. Ongoing warming-induced encroachment by shrubs and trees risks turning this sink into a CO2 source, resulting in a positive feedback on climate warming. To advance mechanistic understanding of how shifts in mycorrhizal types affect long-term carbon (C) and nitrogen (N) stocks, we studied small-scale soil depth profiles of fungal communities and C–N dynamics across a subarctic-alpine forest-heath vegetation gradient. Belowground organic stocks decreased abruptly at the transition from heath to forest, linked to the presence of certain tree-associated ectomycorrhizal fungi that contribute to decomposition when mining N from organic matter. In contrast, ericoid mycorrhizal plants and fungi were associated with organic matter accumulation and slow decomposition. If climatic controls on arctic-alpine forest lines are relaxed, increased decomposition will likely outbalance increased plant productivity, decreasing the overall C sink capacity of displaced tundra.