Male circumcision (MC) reduces penile high-risk human papillomavirus (HR-HPV) on the coronal sulcus and urethra. HR-HPV varies by anatomic site, and it is unknown whether MC decreases HR-HPV on the penile shaft. We assessed the efficacy of MC to reduce HR-HPV on the penile shaft and compared it to known efficacy of MC to reduce HR-HPV on the coronal sulcus. HIV-negative men randomized to receive immediate circumcision (intervention) or circumcision delayed for 24 months (control) were evaluated for HR-HPV at 12 months postenrollment using the Roche HPV Linear Array assay. Among swabs with detectable β-globin or HPV, year 1 HR-HPV prevalence on the coronal sulcus was 21.5% in the intervention arm and 36.3% in the control arm men [adjusted prevalence risk ratios (PRRs) = 0.57, 95% CI 0.39–0.84,p= 0.005]. On the shaft, year 1 HR-HPV prevalence was 15.5% in the intervention and 23.8% in the control arm (adjusted PRR = 0.66, 95% CI 0.39–1.12,p= 0.12). Efficacy of MC to reduce HR-HPV on the shaft was similar to efficacy on the coronal sulcus (p= 0.52). In a sensitivity analysis in which swabs without detectable β-globin or HPV were included as HPV negative, prevalence of HR-HPV on the shaft was lower in the intervention arm (7.8%) than control arm (13.6%; PRR 0.57, 95% CI 0.33–0.99,p< 0.05). HR-HPV was more frequently detected on the coronal sulcus than penile shaft among uncircumcised men (36.3%vs. 23.8%, respectively,p= 0.02) and circumcised men (21.5%vs. 15.5%, respectively,p= 0.24). MC reduced HR-HPV prevalence on both the coronal sulcus and shaft.