Africa’s water needs are often supported by eutrophic water bodies dominated by cyanobacteria posing health threats to riparian populations from cyanotoxins, and Lake Victoria is no exception. In two embayments of the lake (Murchison Bay and Napoleon Gulf), cyanobacterial surveys were conducted to characterize the dynamics of cyanotoxins in lake water and water treatment plants. Forty-six cyanobacterial taxa were recorded, and out of these, fourteen were considered potentially toxigenic (i.e., from the genera Dolichospermum, Microcystis, Oscillatoria, Pseudanabaena and Raphidiopsis). A higher concentration (ranging from 5 to 10 µg MC-LR equiv. L−1) of microcystins (MC) was detected in Murchison Bay compared to Napoleon Gulf, with a declining gradient from the inshore (max. 15 µg MC-LR equiv. L−1) to the open lake. In Murchison Bay, an increase in Microcystis sp. biovolume and MC was observed over the last two decades. Despite high cell densities of toxigenic Microcystis and high MC concentrations, the water treatment plant in Murchison Bay efficiently removed the cyanobacterial biomass, intracellular and dissolved MC to below the lifetime guideline value for exposure via drinking water (<1.0 µg MC-LR equiv. L−1). Thus, the potential health threats stem from the consumption of untreated water and recreational activities along the shores of the lake embayments. MC concentrations were predicted from Microcystis cell numbers regulated by environmental factors, such as solar radiation, wind speed in the N–S direction and turbidity. Thus, an early warning through microscopical counting of Microcystis cell numbers is proposed to better manage health risks from toxigenic cyanobacteria in Lake Victoria.