Despite urban rivers/streams draining into Lake Victoria suffering from urbanization- linked anthropogenic pollution, little is known about their microbiome diversity and structure, or how they respond to intensive anthropogenic inputs. This study conducted a comprehensive analysis of the spatial bacterial community distribution in the sediments of Kisat and Auji streams, that flows through Kisumu City into Lake Victoria's Winam Gulf. Specifically, the study: i) used 16S rRNA gene-based Illumina MiSeq sequencing to determine the diversity and abundance of sediment bacterial communities along the stream catchment impacted by varying levels of urbanisation; ii) determined the presence of potential pathogens and the predicted functional profiles of the sediment bacterial communities in the river to establish their role in the ecosystem, and (iii) identified the key environmental factors (nutritional factors and heavy metals) influencing compositional variations in these communities. The study adopted a stratified purposive sampling, where 22 sediment samples were randomly collected from Lower, Mid and Upper catchment of Auji and Kisat streams, stratified as highly, moderate and non-urbanized zones, respectively, based on land use patterns. Results showed that polluted mid and lower catchment zones stream sediments were highly enriched (p < 0.05) with Actinobacteria and Proteobacteria, and potential pathogen groups such Corynebacterium, Staphylococcus, Cutibacterium, Turicella, Acinetobacter and Micrococcus, including enterics such as Faecalibacterium, Escherichia, Klebsiella, Enterococcus, Prevotella, Legionella, Vibrio and Salmonella. Further, Phylogenetic Investigation of Communities by Reconstruction of Unobserved States (PICRUSt) analysis revealed enrichment of genes associated with carbon and nitrogen metabolism and disease pathogenesis and virulence in the lower and mid catchment zones stream sediment. Physicochemical analyses also showed that the highly urbanized mid and lower stream catchment zones had significantly higher (p < 0.05) total organic carbon (TOC), total nitrogen (TN), and total phosphorous (TP) content, including severely pollution with toxic heavy metals such as lead (Pb), cadmium (Cd), and copper (Cu) than the less urbanized upper catchment zone. Multivariate analysis suggested that TOC, Pb, Cd, TN, pH and Cr were the significant drivers (p < 0.01) of spatial variation in community structure, with Pb, TOC and Cd content being most influential sediment properties (p < 0.01). Overall, these results suggest urban pollution significantly affects the stream sediment microbiome and that the current waste management in Kisumu City is insufficient for the protection of public health and aquatic ecosystems. Therefore, proactive and sustainable urban waste management strategies are needed as the city undergoes rapid urbanization.