Nile tilapia and Nile perch samples from Lake Victoria were analyzed for lindane (gamma-1,2,3,4,5,6-hexachlorocyclohexane), aldrin (1,2,3,4,10,10-hexachloro-1,4,4a,5,8,8a-hexahydro-1,4:5,8-dimethanonaphthalene), α-endosulfan (6,7,8,9,10,10-hexachloro-1,5,5a,6,9,9a-hexahydro-6,9-methano-2,4,3- benzo(e) dioxathiepin-3-oxide), dieldrin (1,2,3,4,10,10-hexachloro-6,7-epoxy-1,4,4a,5,6,7,8,8a-octahydro-1,4,5,8-dimethanonaphthalene), DDE (p,p′-1,1-dichloro-2,2-bis-(4-chlorophenyl)ethylene), and DDT (p,p′-1,1,1-trichloro-2,2-bis-(4-chlorophenyl)ethane). No significant difference (α = 0.05) in the residue levels between fish types for lindane, α-endosulfan, p,p′-DDE, p,p′-DDT, and dieldrin was observed. The aldrin levels in Nile perch (Lates niloticus) were significantly higher than the levels in Nile tilapia (Oreochromis niloticus). No difference was observed in the distribution of residues in the different parts of Nile tilapia, although a difference for p,p′-DDE was observed in the Nile perch. No significant difference was observed in the average fat content of the tissue of Nile perch and Nile tilapia; however, the distribution of fat was significantly different in the different parts of the fish, with the abdominal portion having the highest amount of fat. There was no correlation observed in this study between fat content and organochlorine concentration. Lower p,p′-DDT residues levels compared with the p,p′-DDE levels observed in this study indicate that DDT is no longer in use. The levels of organochlorine pesticide residues found in fish samples in this study were below the FAO, U.S. FDA, Australian, and German extraneous residue limits and maximum residue limits. The concentration of organochlorine residues in surface water within the Napoleon Gulf of Lake Victoria was below detection limit (0.1 μg L−1).