Lake water clarity, phytoplankton biomass, and hypolimnetic oxygen concentration are metrics of water quality that are highly degraded in eutrophic systems. Eutrophication is linked to legacy nutrients stored in catchment soils and in lake sediments. Long lags in water quality improvement under scenarios of nutrient load reduction to lakes indicate an apparent ecosystem memory tied to the interactions between water biogeochemistry and lake sediment nutrients. To investigate how nutrient legacies and ecosystem memory control lake water quality dynamics, we coupled nutrient cycling and lake metabolism in a model to recreate long-term water quality of a eutrophic lake (Lake Mendota, Wisconsin, USA). We modeled long-term recovery of water quality under scenarios of nutrient load reduction and found that the rates and patterns of water quality improvement depended on changes in phosphorus (P) and organic carbon storage in the water column and sediments. Through scenarios of water quality improvement, we showed that water quality variables have distinct phases of change determined by the turnover rates of storage pools – an initial and rapid water quality improvement due to water column flushing, followed by a much longer and slower improvement as sediment P pools were slowly reduced. Water clarity, phytoplankton biomass, and hypolimnetic dissolved oxygen differed in their time responses. Water clarity and algal biomass improved within years of nutrient reductions, but hypolimnetic oxygen took decades to improve. Even with reduced catchment loading, recovery of Lake Mendota to a mesotrophic state may require decades due to nutrient legacies and long ecosystem memory.