We have constructed a nutrient fate model for the Baltic Sea that links anthropogenic nitrogen and phosphorus inputs to the catchment to the dynamics of waterborne loads to the Baltic Sea, covering the time-period from 1900 to present. During this period, nutrient inputs to the drainage basin approximately tripled to a peak in the 1980s, after which they declined. Our model accounts for temporary nutrient storage on land and in inland waters, forming active legacy pools that contribute to nutrient export to the Baltic Sea, and for nutrient removal by terrestrial and aquatic sinks. The model indicates that response times to changes in anthropogenic nutrient inputs to the drainage basin are approximately 4 years for riverine nitrogen and 6–18 years for riverine phosphorus loads. Mineral fertilizer use in agriculture dominates nutrient inputs to the drainage basin, whereas the composition of riverine loads also depends on the collection and treatment of domestic sewage. Removal by terrestrial and aquatic nutrient sinks was the dominant fate of both nitrogen and phosphorus in our model. The amount of nutrients currently stored in legacy pools is therefore much smaller than what the difference between cumulative nutrient inputs to the catchment and the export to the sea suggests. Nevertheless, mobilization from these storage pools is the primary contribution to current anthropogenic riverine nutrient loads to the Baltic Sea. For phosphorus, the legacy effects of past reductions in inputs to the catchment can entail a significant, yet unrealized contribution toward the load reductions stipulated by Baltic Sea management plans. Therefore, accounting for nutrient storage, time-lags, and legacy effects could notably reduce the need for additional future mitigation measures.