This is the first detailed report on the distribution of Ni, As, Sr and Ag in water, sediments and macrophytes from Lake Victoria, complemented with recent data on the heavy metals Cr, Cu, Zn, Cd and Pb. The study was conducted over an 11-month period at five sites in the Kenyan part of Lake Victoria: four sites in the Winam Gulf influenced by various anthropogenic pressures including a site near Kisumu City, and one in the main lake, perceived to have lesser direct anthropogenic influence. Compared with the main lake site, the water in Winam Gulf had significantly higher values for electrical conductivity and concentrations of dissolved components: organic carbon and bound nitrogen, as well as major and most trace elements. This contamination is also evident in surface sediments, which contained significantly higher levels of Cr, Zn, As, Ag, Cd and Pb compared with the main lake site. The mean levels of Cr, Cu, Zn, Ag and Pb exceeded probable effect levels at least at one of the gulf sites. The sediments at the Kisumu City site were classified as severely polluted with Cu (up to 259 mg/kg dw) and Pb (up to 1188 mg/kg dw). The sediment cores showed significantly higher levels of Cu, Zn, Ag, Cd and Pb in the surface (0–3 cm) versus subsurface (22–25 cm) layer at the Kisumu City site, indicating increasing pollution by these elements within the last 15 years. This is also the first report on trace elements in the emergent water plant Vossia cuspidata and submerged plant Ceratophyllum demersum from this lake. Even though the accumulation of most elements is comparable between C. demersum (whole plant) and V. cuspidata roots, the latter shows a better bioindicative potential. Contamination of the gulf with Ni, Cu, Zn, Ag, Cd and Pb is well mirrored in V. cuspidata roots. V. cuspidata strongly restricts the acropetal transport of trace elements, and hence using the shoots as fodder does not pose a risk to livestock.