Background The incidence of HIV infection in young women in Africa is very high. We did a large-scale community-wide phylogenetic study to examine the underlying HIV transmission dynamics and the source and consequences of high rates of HIV infection in young women in South Africa. Methods We did a cross-sectional household survey of randomly selected individuals aged 15–49 years in two neighbouring subdistricts (one urban and one rural) with a high burden of HIV infection in KwaZulu-Natal, South Africa. Participants completed structured questionnaires that captured general demographic, socioeconomic, psychosocial, and behavioural data. Peripheral blood samples were obtained for HIV antibody testing. Samples with HIV RNA viral load greater than 1000 copies per mL were selected for genotyping. We constructed a phylogenetic tree to identify clusters of linked infections (defined as two or more sequences with bootstrap or posterior support ≥90% and genetic distance ≤4·5%). Findings From June 11, 2014, to June 22, 2015, we enrolled 9812 participants, 3969 of whom tested HIV positive. HIV prevalence (weighted) was 59·8% in 2835 women aged 25–40 years, 40·3% in 1548 men aged 25–40 years, 22·3% in 2224 women younger than 25 years, and 7·6% in 1472 men younger than 25 years. HIV genotyping was done in 1589 individuals with a viral load of more than 1000 copies per mL. In 90 transmission clusters, 123 women were linked to 103 men. Of 60 possible phylogenetically linked pairings with the 43 women younger than 25 years, 18 (30·0%) probable male partners were younger than 25 years, 37 (61·7%) were aged 25–40 years, and five (8·3%) were aged 41–49 years: mean age difference 8·7 years (95% CI 6·8–10·6; p<0·0001). For the 92 possible phylogenetically linked pairings with the 56 women aged 25–40 years, the age difference dropped to 1·1 years (95% CI −0·6 to 2·8; p=0·111). 16 (39·0%) of 41 probable male partners linked to women younger than 25 years were also linked to women aged 25–40 years. Of 79 men (mean age 31·5 years) linked to women younger than 40 years, 62 (78·5%) were unaware of their HIV-positive status, 76 (96·2%) were not on antiretroviral therapy, and 29 (36·7%) had viral loads of more than 50 000 copies per mL. Interpretation Sexual partnering between young women and older men, who might have acquired HIV from women of similar age, is a key feature of the sexual networks driving transmission. Expansion of treatment and combination prevention strategies that include interventions to address age-disparate sexual partnering is crucial to reducing HIV incidence and enabling Africa to reach the goal of ending AIDS as a public health threat. Funding President's Emergency Program for AIDS Relief, US Centers for Disease Control and Prevention, South African Medical Research Council, and MAC AIDS Fund.