Multiple nutrient cycles regulate biological nitrogen (N) fixation in forests, yet long-term feedbacks between N-fixation and coupled element cycles remain largely unexplored. We examined soil nutrients and heterotrophic N-fixation across a gradient of 24 temperate conifer forests shaped by legacies of symbiotic N-fixing trees. We observed positive relationships among mineral soil pools of N, carbon (C), organic molybdenum (Mo), and organic phosphorus (P) across sites, evidence that legacies of symbiotic N-fixing trees can increase the abundance of multiple elements important to heterotrophic N-fixation. Soil N accumulation lowered rates of heterotrophic N-fixation in organic horizons due to both N inhibition of nitrogenase enzymes and declines in soil organic matter quality. Experimental fertilization of organic horizon soil revealed widespread Mo limitation of heterotrophic N-fixation, especially at sites where soil Mo was scarce relative to C. Fertilization also revealed widespread absence of P limitation, consistent with high soil P:Mo ratios. Responses of heterotrophic N-fixation to added Mo (positive) and N (negative) were correlated across sites, evidence that multiple nutrient controls of heterotrophic N-fixation were more common than single-nutrient effects. We propose a conceptual model where symbiotic N-fixation promotes coupled N, C, P, and Mo accumulation in soil, leading to positive feedback that relaxes nutrient limitation of overall N-fixation, though heterotrophic N-fixation is primarily suppressed by strong negative feedback from long-term soil N accumulation.