Eutrophication can initiate sudden ecosystem state change either by slowly pushing lakes toward a catastrophic tipping point beyond which self-reinforcing mechanisms establish an alternate stable state, or through rapid but persistent changes in external forcing mechanisms. In principle, these processes can be distinguished by determining whether historical changes in focal parameters (phytoplankton) exhibit transient (rising then declining) or continuously-elevated variability characteristic of alternate stable states or a “paradox of enrichment,” respectively. We tested this hypothesis in the south basin of Lake Winnipeg, Canada, a site with intense blooms of N2-fixing cyanobacteria since 1990, but for which little is known of earlier limnological conditions, causes of eutrophication, or whether modern conditions represent a alternate stable state. Paleolimnological analysis revealed that the basin was naturally mesotrophic (∼15–20 μg P L−1) with diazotrophic cyanobacteria, productive diatoms, and phosphorus-rich sediments. Eutrophication accelerated during ca.1900–ca.1990, when sedimentary nitrogen, phosphorus and carbon contents increased 10–50%, δ15N enriched 3–4‰, and concentrations of many fossil pigments increased 300–500%. Nearly 75% of 20th century variability was explained by concomitant increases in production of livestock and crops, but not by climate. After ca.1990, the basin exhibited a rapid threefold increase in akinetes from Aphanizomenon and Anabaena spp. and 50% declines in pigments from chlorophytes and cyanobacteria because of sudden socio-economic reorganization of agriculture. Phytoplankton variability quantified using Gaussian generalized additive models increased continuously since the onset of agriculture for bloom-forming taxa, did not decline after state change, and suggested that recovery should not be affected by stable-state hysteresis.