BACKGROUND: Beliefs about gender roles and high-risk sexual behaviours underlie the human immunodeficiency virus (HIV) epidemic in South Africa. Yet, there is limited information on the relationships between beliefs about gender roles and risky sexual behaviours. Few studies have explored the association between beliefs about gender roles, high risk sexual behaviour, and health-seeking behaviour among men. METHODS: We investigated associations between gender beliefs (dichotomised as traditional or progressive) and high-risk sexual behaviour among South African men presenting for medical male circumcision (Apr 2014 to Nov 2015). RESULTS: Of 2792 enrolled men, 47.4% reported traditional gender beliefs. Participant ages ranged between 18-46 years (median age 26 years; interquartile range, 21-31 years). Most participants had at least one sex partner over the last 12 months (68.2%). Younger men (18-24 years old vs. 25-46 years old) (odds ratio [OR], 1.5 [95% confidence interval (CI) 1.0-2.0]), those with multiple partners ([OR], 1.5 (CI) 1.3-1.8]) and participants unsure of their last partner's HIV status (OR, 1.4 [95% CI 1.1-1.7]) were more likely to have traditional beliefs on gender roles. CONCLUSION: Young men with traditional beliefs on gender roles may be more likely to engage in high-risk sexual behaviour and could be good candidates for HIV prevention programmes. N = 206 (max 350) Trial registration Name of registry: Clinicaltrials.gov; Trial registration number: NCT02352961; Date of registration: 30 January 2015 "Retrospectively registered"; URL of trial registry record: https://www.clinicaltrials.gov/.