Nitrogen (N) from anthropogenic sources has dramatically increased in terrestrial ecosystems globally. Although belowground microbial processes and events that release N into the atmosphere, such as fire, could support ecosystem resilience to eutrophication, little is known about how these factors might affect N loss following chronic fertilization, thus promoting ecosystem recovery. We studied how N pools, N-cycling potential rates and their affiliated microbial populations, and microbial community composition responded to the factorial effects of cessation of 30 years of chronic N fertilization and annual burning at a tallgrass prairie. Soil N availability in previously fertilized plots recovered by 86% (using never-fertilized control plots as a 100% recovery reference), while plant and microbial biomass did not change. Nitrification potential recovered (80%), and denitrification potential partially recovered (50%), in previously fertilized plots. There were differential responses among key groups of nitrifiers (archaea vs. bacteria) and denitrifiers (nosZ clade I vs. clade II from Anaeromyxobacter dehalogenans) to long-term N fertilization and cessation despite the whole microbial community composition not shifting significantly after fertilization ceased. Also, N-cycling potentials were consistently higher in unburned prairie. Together, results suggest that fire is a prominent mechanism for ecosystem N removal in annually burned prairie, while N-cycling microbes will have an important role in the absence of fire; however, the recovery to pre-fertilized condition, with or without fire, will take longer than 1 year. Overall, differential resilience of biotic populations and processes can potentially shape different outcomes of soil N loss and tallgrass prairie ecosystem recovery from long-term N fertilization.