BACKGROUND: Understanding how social contexts shape HIV risk will facilitate development of effective prevention responses. Social cohesion, the trust and connectedness experienced in communities, has been associated with improved sexual health and HIV-related outcomes, but little research has been conducted in high prevalence settings. METHODS: We conducted population-based surveys with adults 18-49 in high HIV prevalence districts in Mpumalanga (n = 2057) and North West Province (n = 1044), South Africa. Community social cohesion scores were calculated among the 70 clusters. We used multilevel logistic regression stratified by gender to assess individual- and group-level associations between social cohesion and HIV-related behaviors: recent HIV testing, heavy alcohol use, and concurrent sexual partnerships. RESULTS: Group-level cohesion was protective in Mpumalanga, where perceived social cohesion was higher. For each unit increase in group cohesion, the odds of heavy drinking among men were reduced by 40% (95%CI 0.25, 0.65); the odds of women reporting concurrent sexual partnerships were reduced by 45% (95%CI 0.19, 1.04; p = 0.06); and the odds of reporting recent HIV testing were 1.6 and 1.9 times higher in men and women, respectively. CONCLUSIONS: We identified potential health benefits of cohesion across three HIV-related health behaviors in one region with higher overall evidence of group cohesion. There may be a minimum level of cohesion required to yield positive health effects.