We used a dynamic, long-term mass balance approach to track cumulative carbon (C) and nitrogen (N) losses to fire in boreal Manitoba over the 6500 years since deglaciation. Estimated C losses to decomposition and fire, combined with measurements of N pools in mature and burned forest floors, suggest that loss of N by combustion has likely resulted in a long-term loss that exceeds the amount of N stored in soil today by 2 to 3 times. These estimates imply that biological N fixation rates could be as high as 5 to 10 times atmospheric deposition rates in boreal regions. At the site scale, the amount of N lost is due to N content of fuels, which varies by stand type and fire severity, which in turn vary with climate and fire dynamics. The interplay of fire frequency, fire severity, and N partitioning during regrowth are important for understanding rates and sustainability of nutrient and carbon cycling over millenia and over broad regions.