This is the first comprehensive report on the accumulation of Cr, Ni, As, and Ag in the fish species Nile tilapia Oreochromis niloticus and Nile perch Lates niloticus from Lake Victoria, complemented with recent data on Cu, Zn, Cd, and Pb. This also is the first report on Cr, Ni, As, and Ag levels in invertebrates: the shrimp Caridina nilotica , gastropod Pila ovata , and bivalve Mutela bourguignati . The study was conducted at five sites in the Kenyan part of Lake Victoria: four sites in Winam Gulf influenced by various anthropogenic pressures, including a site near Kisumu City, and one in the main lake, with lesser direct anthropogenic influence. Apart from Cu and Ag, which were highest in O. niloticus liver, the invertebrates had higher levels of trace elements than fish. Contamination of the gulf with trace elements was best mirrored by the invertebrates, whose mobility is limited; they accumulated Cr, Cd, Ag, and Pb corresponding to the levels in the surface sediment. The accumulation of trace elements in fish species and their bioindicative potential corresponded to their habitats and feeding behaviour. The tissue contents of most trace elements were higher in the inshore-dwelling, omnivorous O . niloticus compared to the pelagic, piscivorous L . niloticus . Cu (465 ± 689 mg/kg dw) and Ag (3.45 ± 1.49 mg/kg dw) in the liver of O . niloticus were up to 10 and 119 times higher than in L . niloticus , respectively. Oreochromis niloticus therefore has bioindicative potential for Cu and Ag contamination. Both the invertebrates and fish showed positive correlations between Cu and Ag concentrations, indicating similar source and/or uptake route. The target hazard quotients (THQ) show that there is no human health risk associated with the consumption of these fish. However, the levels of Zn, Cd, and Pb in P. ovata surpassed maximum food safety limits and are hence potentially unsafe for human consumption. Electronic supplementary material The online version of this article (10.1007/s00244-020-00715-0) contains supplementary material, which is available to authorized users.