BACKGROUND: Fishing communities around Lake Victoria in sub-Saharan Africa have been characterised as a population at high risk of HIV-infection. METHODS: Using data from a cohort of HIV-positive individuals aged 13-49 years, enrolled from 5 fishing communities on Lake Victoria between 2009-2011, we sought to identify factors contributing to the epidemic and to understand the underlying structure of HIV transmission networks. Clinical and socio-demographic data were combined with HIV-1 phylogenetic analyses. HIV-1 gag-p24 and env-gp-41 sub-genomic fragments were amplified and sequenced from 283 HIV-1-infected participants. Phylogenetic clusters with ≥2 highly related sequences were defined as transmission clusters. Logistic regression models were used to determine factors associated with clustering. RESULTS: Altogether, 24% (n = 67/283) of HIV positive individuals with sequences fell within 34 phylogenetically distinct clusters in at least one gene region (either gag or env). Of these, 83% occurred either within households or within community; 8/34 (24%) occurred within household partnerships, and 20/34 (59%) within community. 7/12 couples (58%) within households clustered together. Individuals in clusters with potential recent transmission (11/34) were more likely to be younger 71% (15/21) versus 46% (21/46) in un-clustered individuals and had recently become resident in the community 67% (14/21) vs 48% (22/46). Four of 11 (36%) potential transmission clusters included incident-incident transmissions. Independently, clustering was less likely in HIV subtype D (adjusted Odds Ratio, aOR = 0.51 [95% CI 0.26-1.00]) than A and more likely in those living with an HIV-infected individual in the household (aOR = 6.30 [95% CI 3.40-11.68]). CONCLUSIONS: A large proportion of HIV sexual transmissions occur within house-holds and within communities even in this key mobile population. The findings suggest localized HIV transmissions and hence a potential benefit for the test and treat approach even at a community level, coupled with intensified HIV counselling to identify early infections.