Nitrogen fertilizer management can impact soil organic C (SOC) stocks in cereal-based cropping systems by regulating crop residue inputs and decomposition rates. However, the impact of long-term N fertilizer management, and associated changes in SOC quantity and quality, on the fate of N fertilizer inputs is uncertain. Using two 15-year N fertilizer rate experiments on continuous maize (Zea mays L.) in Iowa, which have generated gradients of SOC, we evaluated the legacy effects of N fertilizer inputs on the fate of added N. Across the historical N fertilizer rates, which ranged from 0 to 269 kg N ha−1 yr−1, we applied isotopically-labeled N fertilizer at the empirically-determined site-specific agronomic optimum rate (202 kg N ha−1 at the central location and 269 kg N ha−1 at the southern location) and measured fertilizer recovery in crop and soil pools, and, by difference, environmental losses. Crop fertilizer N recovery efficiency (NREcrop) at physiological maturity averaged 44% and 14% of applied N in central Iowa and southern Iowa, respectively (88 kg N ha−1 and 37 kg N ha−1, respectively). Despite these large differences in NREcrop, the response to historical N rate was remarkably similar across both locations: NREcrop was greatest at low and high historical N rates, and least at the intermediate rates. Decreasing NREcrop from low to intermediate historical N rates corresponded to a decline in early-season fertilizer N recovery in the relatively slow turnover topsoil mineral-associated organic matter pool (0–15 cm), while increasing NREcrop from intermediate to high historical N rates corresponded to an increase in early-season fertilizer N recovery in the relatively fast turnover topsoil particulate organic matter pool and an increase in crop yield potential. Despite the variation in NREcropalong the historical N rate gradient, we did not detect an effect of historical N rate on environmental losses during the growing season, which averaged 34% and 69% of fertilizer N inputs at the central and southern locations, respectively (69 kg N ha−1 and 185 kg N ha−1, respectively). Our results suggest that, while beneficial for SOC storage over the long term, fertilizing at the agronomic optimum N rate can lead to significant environmental N losses.