In contrast to the well-recognized permafrost carbon (C) feedback to climate change, the fate of permafrost nitrogen (N) after thaw is poorly understood. According to mounting evidence, part of the N liberated from permafrost may be released to the atmosphere as the strong greenhouse gas (GHG) nitrous oxide (N2O). Here, we report post-thaw N2O release from late Pleistocene permafrost deposits called Yedoma, which store a substantial part of permafrost C and N and are highly vulnerable to thaw. While freshly thawed, unvegetated Yedoma in disturbed areas emit little N2O, emissions increase within few years after stabilization, drying and revegetation with grasses to high rates (548 (133–6286) μg N m−2 day−1; median with (range)), exceeding by 1–2 orders of magnitude the typical rates from permafrost-affected soils. Using targeted metagenomics of key N cycling genes, we link the increase in in situ N2O emissions with structural changes of the microbial community responsible for N cycling. Our results highlight the importance of extra N availability from thawing Yedoma permafrost, causing a positive climate feedback from the Arctic in the form of N2O emissions.