"Men, Together Making a Difference!" is an HIV/STD risk-reduction intervention that significantly increased self-reported consistent condom use during vaginal intercourse compared with a health-promotion attention-control intervention among men (N = 1181) in Eastern Cape Province, South Africa. The present analyses were designed to identify mediators of the intervention's efficacy. The potential mediators were Social Cognitive Theory (SCT) constructs that the intervention targeted, including several aspects of condom-use self-efficacy, outcome expectancies, and knowledge. Mediation was assessed using a product-of-coefficients approach where an α path (the intervention's effect on the potential mediator) and a β path (the potential mediator's effect on the outcome of interest, adjusting for intervention) were estimated independently in a generalized estimating equations framework. Condom-use negotiation self-efficacy, technical-skill self-efficacy, and impulse-control self-efficacy were significant mediators. Although not mediators, descriptive norm and expected friends' approval of condom use predicted subsequent self-reported condom use, whereas the expected approval of sexual partner did not. The present results suggest that HIV/STD risk-reduction interventions that draw upon SCT and that address self-efficacy to negotiate condom use, to apply condoms correctly, and to exercise sufficient control when sexually aroused to use condoms may contribute to efforts to reduce sexual risk behavior among South African men. Future research must examine whether approaches that build normative support for condom use among men's friends are also efficacious.