Introduction Mozambique continues to have a significant burden of HIV. Developing strategies to control the HIV epidemic remains a key priority for the Mozambican public health community. The primary aim of this study was to determine HIV prevalence and risk behavior among males and females screened for a HIV vaccine preparedness study in Maputo, Mozambique. Methods Male and female participants between 18–35 years old were recruited from the general community and from female sex worker (FSW) and lesbian, gay, bisexual, and transgender (LGBT) associations in Maputo. All participants were screened for HIV and a questionnaire was administered to each participant to assess HIV risk behavior. Results A total of 1125 adults were screened for HIV infection, among whom 506 (45%) were male. Among men, 5.7% reported having had sex with men (MSM) and 12% of female participants reported having exchanged sex for money, goods or favors in the past 3 months. The overall HIV prevalence was 10.4%; 10.7% of women, and 10.1% of men were HIV infected; 41.4% of MSM were seropositive. HIV infection was associated with older age (25–35 years old) (OR: 6.13, 95% CI: 3.01, 12.5), MSM (OR: 9.07, 95% CI: 3.85, 21.4), self-perception of being at high-risk for HIV (OR: 3.99, 95% CI: 1.27, 12.5) and self-report of a history of a diagnosis of sexually transmitted infection (OR: 3.75, 95% CI: 1.57, 8.98). Conclusion In our cohort, HIV prevalence was much higher among MSM compared to the overall prevalence. Behavioral factors were found to be more associated with HIV prevalence than demographic factors. The study findings demonstrate the critical importance of directing services to minority communities, such as MSM, when prevention strategies are being devised for the general population.