Unprecedented decreases in atmospheric nitrogen (N) deposition together with increases in agricultural N-use efficiency have led to decreases in net anthropogenic N inputs in many eastern US and Canadian watersheds as well as in Europe. Despite such decreases, N concentrations in streams and rivers continue to increase, and problems of coastal eutrophication remain acute. Such a mismatch between N inputs and outputs can arise due to legacy N accumulation and subsequent lag times between implementation of conservation measures and improvements in water quality. In the present study, we quantified such lag times by pairing long-term N input trajectories with stream nitrate concentration data for 16 nested subwatersheds in a 6800 km2, Southern Ontario watershed. Our results show significant nonlinearity between N inputs and outputs, with a strong hysteresis effect indicative of decadal-scale lag times. The mean annual lag time was found to be 24.5 years, with lags varying seasonally, likely due to differences in N-delivery pathways. Lag times were found to be negatively correlated with both tile drainage and watershed slope, with tile drainage being a dominant control in fall and watershed slope being significant during the spring snowmelt period. Quantification of such lags will be crucial to policy-makers as they struggle to set appropriate goals for water quality improvement in human-impacted watersheds.