HIV incidence in eastern and southern Africa has historically been concentrated among girls and women aged 15-24 years. As new cases decline with HIV interventions, population-level infection dynamics may shift by age and gender. Here, we integrated population-based surveillance of 38,749 participants in the Rakai Community Cohort Study and longitudinal deep-sequence viral phylogenetics to assess how HIV incidence and population groups driving transmission have changed from 2003 to 2018 in Uganda. We observed 1,117 individuals in the incidence cohort and 1,978 individuals in the transmission cohort. HIV viral suppression increased more rapidly in women than men, however incidence declined more slowly in women than men. We found that age-specific transmission flows shifted: whereas HIV transmission to girls and women (aged 15-24 years) from older men declined by about one-third, transmission to women (aged 25-34 years) from men that were 0-6 years older increased by half in 2003 to 2018. Based on changes in transmission flows, we estimated that closing the gender gap in viral suppression could have reduced HIV incidence in women by half in 2018. This study suggests that HIV programmes to increase HIV suppression in men are critical to reduce incidence in women, close gender gaps in infection burden and improve men's health in Africa.