Lake Victoria, the largest tropical lake in the world, suffers from severe eutrophication and the probable extinction of up to half of its 500+ species of endemic cichlid fishes. The continuing degradation of Lake Victoria's ecological functions has serious long-term consequences for the ecosystem services it provides, and may threaten social welfare in the countries bordering its shores. Evaluation of recent ecological changes in the context of aquatic food-web alterations, catchment disturbance and natural ecosystem variability has been hampered by the scarcity of historical monitoring data. Here, we present high-resolution palaeolimnological data, which show that increases in phytoplankton production developed from the 1930s onwards, which parallels human-population growth and agricultural activity in the Lake Victoria drainage basin. Dominance of bloom-forming cyanobacteria since the late 1980s coincided with a relative decline in diatom growth, which can be attributed to the seasonal depletion of dissolved silica resulting from 50 years of enhanced diatom growth and burial. Eutrophication-induced loss of deep-water oxygen started in the early 1960s, and may have contributed to the 1980s collapse of indigenous fish stocks by eliminating suitable habitat for certain deep-water cichlids. Conservation of Lake Victoria as a functioning ecosystem is contingent upon large-scale implementation of improved land-use practices.