Lake Victoria, which is the largest fresh water lake in Africa, represents a unique ecosystem that has the largest fresh water fishery in the continent. However, increased anthropogenic activities has increased the potential pollution of the lake especially the heavy metal pollutants which may be toxic to humans and aquatic fauna. There is need therefore for continuous monitoring of pollution levels in the lake. Samples of water, soil sediments and algae were collected in dry, long and short rainy periods of 2008 and analyzed for heavy metal by Atomic Absorption Spectrophotometry. The highest concentration of trace metals were found in sediment samples with Zn having the highest mean concentration values in both Winam (1.019 ppm) and Mwanza gulf (0.889 ppm). The mean concentration of Pb was higher in water samples from Winam gulf (0.823 ppm), while Hg in microalgae samples from Winam gulf had a mean concentration of 0.000148 ppm. The highest concentration of Zn (1.589 ppm) was determined in the sediment samples from Kirumba bay of the Mwanza gulf and the lowest was in sediments from Kishimba bay (0.327 ppm). Levels of trace metals in microalgae were not significant in different sites of the Mwanza Gulf. Like in the Mwanza gulf, levels of Zn was high in sediments from all the sites sampled in Winam Gulf, the highest recorded at Kisat. Pb levels were highest in the water samples from Hippo point, whereas concentration levels of Cd, Cr and Hg were lowest in all the four sites sampled. The maximum biomass of microalgae occurred at Kisat during the short rain season (November-December) followed by Kamito in the same season.VicRes through the Inter- University Council of East Africa (ICUEA) for sustainable management of Lake Victoria resource