A community-based needs assessment among men who have sex with men (MSM) in South Africa found that 27 % (n = 280/1,045) of MSM had never been tested for HIV. The most frequently reported reasons for not having been tested were the perception of not being at risk (57 %) and fear of being tested (52 %). This article explores factors associated with these two reasons among the untested MSM. In multiple logistic regressions, the perception of not being at risk of HIV infection was negatively associated with being black, coloured or Indian, being sexually active, knowing people living with HIV, and a history of sexually transmitted infections (STIs) in the past 24 months (adj. OR = .24, .32, .38, and .22, respectively). Fear of being tested for HIV was positively associated with being black, coloured or Indian, preferred gender expression as feminine, being sexually active, a history of STIs, and experience of victimization on the basis of sexual orientation (adj. OR = 2.90, 4.07, 4.62, 5.05, and 2.34, respectively). Results suggest that HIV prevention programs directed at South African MSM will be more effective if testing and treatment of STIs are better integrated into HIV testing systems. Finally, social exclusion on the basis of race and sexual orientation ought to be addressed in order to reach hidden, at-risk, populations of MSM.