BACKGROUND: In 2012, South Africa set a goal of circumcising 4.3 million men ages 15-49 by 2016. By the end of March 2014, 1.9 million men had received voluntary medical male circumcision (VMMC). In an effort to accelerate progress, South Africa undertook a modeling exercise to determine whether circumcising specific client age groups or geographic locations would be particularly impactful or cost-effective. Results will inform South Africa's efforts to develop a national strategy and operational plan for VMMC. METHODS AND FINDINGS: The study team populated the Decision Makers' Program Planning Tool, Version 2.0 (DMPPT 2.0) with HIV incidence projections from the Spectrum/AIDS Impact Module (AIM), as well as national and provincial population and HIV prevalence estimates. We derived baseline circumcision rates from the 2012 South African National HIV Prevalence, Incidence and Behaviour Survey. The model showed that circumcising men ages 20-34 offers the most immediate impact on HIV incidence and requires the fewest circumcisions per HIV infection averted. The greatest impact over a 15-year period is achieved by circumcising men ages 15-24. When the model assumes a unit cost increase with client age, men ages 15-29 emerge as the most cost-effective group. When we assume a constant cost for all ages, the most cost-effective age range is 15-34 years. Geographically, the program is cost saving in all provinces; differences in the VMMC program's cost-effectiveness across provinces were obscured by uncertainty in HIV incidence projections. CONCLUSION: The VMMC program's impact and cost-effectiveness vary by age-targeting strategy. A strategy focusing on men ages 15-34 will maximize program benefits. However, because clients older than 25 access VMMC services at low rates, South Africa could consider promoting demand among men ages 25-34, without denying services to those in other age groups. Uncertainty in the provincial estimates makes them insufficient to support geographic targeting.