Total mercury (THg) concentration was analysed in muscles of common fish species of Lake Victoria in the eastern and southern parts of the lake using cold vapour Atomic Absorption Spectrophotometric technique. Mercury concentration in all fish species was generally lower than the WHO maximum allowable concentration (500 ng/g ww) in edible fish parts. The maximum concentration of THg in Lates niloticus samples was 396 ng/g ww. Samples of Oreochromis niloticus had THg concentration ranging between <0.01 and 419 ng/g ww. Clarias gariepinus had THg concentration ranging between 1.2 and 239.1 ng/g ww. All less common fish species, such as, Labeo victirianus, Synodontis victoriae, Oreochromis leucostictus, Schilbe intermedius, Brycinus jacksonii, B. sadleri, Tilapia rendalii, Tilapia zilii and Haplochromines had THg concentration below the WHO maximum allowable limit (500 ng/g ww). The study showed that Hg from small-scale gold mining activities in Lake Victoria basin is not transported to the lake by fluvial discharge. Other possible pathways of Hg input to Lake Victoria are discussed.