Discerning ecosystem change and food web dynamics underlying anthropogenic eutrophication and the introduction of non-native species is necessary for ensuring the long-term sustainability of fisheries and lake biodiversity. Previous studies of eutrophication in Lake Victoria, eastern Africa, have focused on the loss of endemic fish biodiversity over the past several decades, but changes in the plankton communities over this same time remain unclear. To fill this gap, we examined sediment cores from a eutrophic embayment, Mwanza Gulf, to determine the timing and magnitude of changes in the phytoplankton and zooplankton assemblages over the past century. Biogeochemical proxies indicate nutrient enrichment began around ~ 1920 CE and led to rapid increases in primary production, and our analysis of photosynthetic pigments revealed three zones: pre-eutrophication (prior to 1920 CE), onset of eutrophication with increases in all pigments (1920–1990 CE), and sustained eutrophication with cyanobacterial dominance (1990 CE–present). Cladoceran remains indicate an abrupt decline in biomass in ~ 1960 CE, in response to the cumulative effects of eutrophication and lake-level rise, preceding the collapse of haplochromine cichlids in the 1980s. Alona and Chydorus, typically benthic littoral taxa, have remained at relatively low abundances since the 1960s, whereas the abundance of Bosmina, typically a planktonic taxon, increased in the 1990s concurrently with the biomass recovery of haplochromine cichlid fishes. Overall, our results demonstrate substantial changes over the past century in the biomass structure and taxonomic composition of Mwanza Gulf phytoplankton and zooplankton communities, providing a historical food web perspective that can help understand the recent changes and inform future resource management decisions in the Lake Victoria ecosystem.