Extended-Spectrum Beta-Lactamase (ESBL)-producing bacteria are a common cause of healthcare and community-associated infections worldwide. The distribution of such isolates in the environment and their presence in fish as a result of sewage contamination is not well-studied. Here we examined fish and environmental samples from Mwanza city for the presence of ESBL-producing bacteria. From 196 fish sampled from local markets, 26 (13.3%) contained lactose-fermenting ESBL-producing bacteria, while 39/73 (53.4%) environmental samples from the same area were ESBL producers. Antibiotic resistance genes, multi locus sequence types (MLST) and plasmid replicon types in 24 selected isolates from both populations were identified with whole genome sequencing using Illumina MiSeq. Nine of eleven sequenced fish isolates had the blaCTX-M-15 gene whereas 12/13 from environment carried blaCTX-M-15. Antibiotic resistance genes encoding resistance to sulfonamides (sul1/sul2), tetracyclines [tet(A)/tet(B)] fluoroquinolones [e.g., aac(6′)-Ib-cr, qnrS1], aminoglycosides [e.g., aac(3)-lld, strB, strA,] and trimethoprim (e.g., dfrA14) were detected. E. coli sequence type ST-38 (2) and ST-5173 (2) were detected in isolates both from the environment and fish. IncY plasmids carrying blaCTX-M-15, qnrS1, strA, and strB were detected in five environmental E. coli isolates and in one E. coli isolate from fish. Our data indicate spillage of resistant environmental isolates into Lake Victoria through the sewage system. Persistence of blaCTX-M-15 in the Mwanza city environment is complex, and involves both clonal spread of resistant strains as well as dissemination by commonly occurring IncY plasmids circulating in isolates present in humans, the environment as well as in the food chain.