There is growing evidence that the release of phosphorus (P) from “legacy” stores can frustrate efforts to reduce P loading to surface water from sources such as agriculture and human sewage. Less is known, however, about the magnitude and residence times of these legacy pools. Here we constructed a budget of net anthropogenic P inputs to the Baltic Sea drainage basin and developed a three-parameter, two-box model to describe the movement of anthropogenic P though temporary (mobile) and long-term (stable) storage pools. Phosphorus entered the sea as direct coastal effluent discharge and via rapid transport and slow, legacy pathways. The model reproduced past waterborne P loads and suggested an ~30-year residence time in the mobile pool. Between 1900 and 2013, 17 and 27 Mt P has accumulated in the mobile and stable pools, respectively. Phosphorus inputs to the sea have halved since the 1980s due to improvements in coastal sewage treatment and reductions associated with the rapid transport pathway. After decades of accumulation, the system appears to have shifted to a depletion phase; absent further reductions in net anthropogenic P input, future waterborne loads could decrease. Presently, losses from the mobile pool contribute nearly half of P loads, suggesting that it will be difficult to achieve substantial near-term reductions. However, there is still potential to make progress toward eutrophication management goals by addressing rapid transport pathways, such as overland flow, as well as mobile stores, such as cropland with large soil-P reserves.