Men's gender role conflict and stress (GRC/S), the psychological strain they experience around fulfilling expectations of themselves as men, has been largely unexplored in HIV prevention research. We examined associations between both men's gender norms and GRC/S and three HIV risk behaviors using data from a population-based survey of 579 18-35 year-old men in rural northeast South Africa. Prevalence of sexual partner concurrency and intimate partner violence (IPV) perpetration in the last 12 months were 38.0 and 13.4%, respectively; 19.9% abused alcohol. More inequitable gender norms and higher GRC/S were each significantly associated with an increased odds of concurrency (p = 0.01; p < 0.01, respectively), IPV perpetration (p = 0.03; p < 0.01), and alcohol abuse (p = 0.02; p < 0.001), controlling for demographic characteristics. Ancillary analyses demonstrated significant positive associations between: concurrency and the GRC/S sub-dimension subordination to women; IPV perpetration and restrictive emotionality; and alcohol abuse and success, power, competition. Programs to transform gender norms should be coupled with effective strategies to prevent and reduce men's GRC/S.