Stigma remains a significant barrier to HIV testing in South Africa. Despite being a social construct, most HIV-stigma research focuses on individuals; further the intersection of gender, testing and stigma is yet to be fully explored. We examined the relationship between anticipated stigma at individual and community levels and recent testing using a population-based sample (n = 1126) in Mpumalanga, South Africa. We used multi-level regression to estimate the potential effect of reducing community-level stigma on testing uptake using the g-computation algorithm. Men tested less frequently (OR 0.22, 95% CI 0.14-0.33) and reported more anticipated stigma (OR 5.1, 95% CI 2.6-10.1) than women. For men only, testing was higher among those reporting no stigma versus some (OR 1.40, 95% CI 0.97-2.03; p = 0.07). For women only, each percentage point reduction in community-level stigma, the likelihood of testing increased by 3% (p < 0.01). Programming should consider stigma reduction in the context of social norms and gender to tailor activities appropriately.