OBJECTIVES: To estimate the prevalence of circumcision among young men in rural Mwanza, North-Western Tanzania, and document trends in circumcision prevalence over time. To investigate associations of circumcision with socio-demographic characteristics, reported sexual behaviours and sexually transmitted infections (STIs). DESIGN: A cross-sectional survey in communities which had previously participated in a cluster-randomized trial of an adolescent sexual health intervention that did not include male circumcision in 20 rural communities. METHODS: In 2007/08, 7300 young men (age 16-23 years) were interviewed and examined by a clinician. The prevalence of circumcision by age was compared with data collected during the trial in 1998-2002. Odds ratios (OR) and 95% confidence intervals (CI) for the association of circumcision with socio-demographic characteristics, reported sexual behaviours and with HIV and other STIs were estimated using multivariable conditional logistic regression. RESULTS: The prevalence of male circumcision was 40.6%, and age-specific prevalence had more than doubled since 2001/2002. Circumcised men reported less risky sexual behaviours, being more likely to report having ever used a condom (adjusted OR = 2.62, 95%CI:2.32-2.95). Men circumcised before sexual debut were at reduced risk of being HIV seropositive compared with non-circumcised men (adjusted OR = 0.50, 95%CI:0.25-0.97), and also had reduced risks of HSV-2 infection and genital ulcer syndrome in the past 12 months compared with non-circumcised men. CONCLUSIONS: There was a steep increase in circumcision prevalence between 2001/02 and 2007/08 in the absence of a promotional campaign. Circumcised men reported safer sexual practices than non-circumcised men and had lower prevalence of HIV and HSV-2 infection.