Nitrogen (N) availability exerts strong control on carbon storage in the forests of Northern Eurasia. Here, using a process-based model, we explore how three factors that alter N availability-permafrost degradation, atmospheric N deposition, and the abandonment of agricultural land to forest regrowth (land-use legacy)-affect carbon storage in the region's forest vegetation over the 21st century within the context of two IPCC global-change scenarios (RCPs 4.5 and 8.5). For RCP4.5, enhanced N availability results in increased tree carbon storage of 27.8 Pg C, with land-use legacy being the most important factor. For RCP8.5, enhanced N availability results in increased carbon storage in trees of 13.4 Pg C, with permafrost degradation being the most important factor. Our analysis reveals complex spatial and temporal patterns of regional carbon storage. This study underscores the importance of considering carbon-nitrogen interactions when assessing regional and sub-regional impacts of global change policies.