The Mpumalanga Men's Study (MPMS) is the assessment of the Project Boithato HIV prevention intervention for South African MSM. Boithato aims to increase consistent condom use, regular testing for HIV-negative MSM, and linkage to care for HIV-positive MSM. The MPMS baseline examined HIV prevalence and associated risk behaviors, and testing, care, and treatment behaviors among MSM in Gert Sibande and Ehlanzeni districts in Mpumalanga province, South Africa in order to effectively target intervention activities. We recruited 307 MSM in Gert Sibande and 298 in Ehlanzeni through respondent-driven sampling (RDS) between September 2012-March 2013. RDS-adjusted HIV prevalence estimates are 28.3% (95% CI 21.1%-35.3%) in Gert Sibande, and 13.7% (95% CI 9.1%-19.6%) in Ehlanzeni. Prevalence is significantly higher among MSM over age 25 [57.8% (95% CI 43.1%-72.9%) vs. 17.9% (95% CI 10.6%-23.9%), P<0.001 in Gert Sibande; 34.5% (95%CI 20.5%-56.0%) vs. 9.1% (95% CI 4.6%-13.9%), P<0.001 in Ehlanzeni]. In Gert Sibande, prevalence is higher among self-identified gay and transgender MSM vs. other MSM [39.3% (95%CI, 28.3%-47.9%), P<0.01], inconsistent condom users [38.1% (18.1%-64.2%), P<0.05], those with a current regular male partner [35.0% (27.1%-46.4%), P<0.05], and those with lifetime experience of intimate partner violence with men [40.4%, (95%CI 28.9%-50.9%), P<0.05]. Prevalence of previous HIV testing was 65.8% (95%CI 58.8%-74.0%) in Gert Sibande, and 69.3% (95%CI 61.9%-76.8%) in Ehlanzeni. Regular HIV testing was uncommon [(34.6%, (95%CI 27.9%-41.4%) in Gert Sibande; 31.0% (95%CI 24.9%-37.8%) in Ehlanzeni]. Among HIV-positive participants, few knew their status (28.1% in Gert Sibande and 14.5% in Ehlanzeni), or were appropriately linked to care (18.2% and 11.3%, respectively), or taking antiretroviral therapy (13.6% and 9.6% respectively). MPMS results demonstrate the importance of implementing interventions for MSM to increase consistent condom use, regular HIV testing, and linkage and engagement in care for HIV-infected MSM.