We estimated HIV prevalence and identified correlates of HIV infection among 1106 men and women aged 16–34 years residing in Kisumu, Kenya. Demographic, sexual, and other behavioural data were collected using audio computer-assisted self-interview in conjunction with a medical examination, real-time parallel rapid HIV testing, and laboratory testing for pregnancy, gonorrhoea, chlamydia, syphilis, and herpes simplex virus type 2. Multivariate logistic regression was used to identify variables associated with prevalent HIV infection by gender. Overall HIV prevalence was 12.1%. HIV prevalence among women (17.1%) was approximately two-and-one-half times the prevalence among men (6.6%). Odds of HIV infection in men increased with age (aOR associated with one-year increase in age = 1.21, CI = 1.07–1.35) and were greater among those who were uncircumcised (aOR = 4.42, CI = 1.41–13.89) and those who had an herpes simplex virus type 2-positive (aOR = 3.13, CI = 1.12–8.73) test result. Odds of prevalent HIV infection among women also increased with age (aOR associated with one-year increase in age = 1.16, CI = 1.04–1.29). Women who tested herpes simplex virus type 2 positive had more than three times the odds (aOR = 3.85, CI = 1.38–10.46) of prevalent HIV infection compared with those who tested herpes simplex virus type 2 negative. Tailored sexual health interventions and programs may help mitigate HIV age and gender disparities.