Current HIV vaccines in development appear unlikely to prevent infection, but could provide benefits by increasing survival; such vaccines are described as disease-modifying vaccines. We review the current status of vaccines and modeling vaccines. We also predict the impact that disease-modifying vaccines could have in South Africa, where multiple subtypes are co-circulating. We model transmissibility/fitness differences among subtypes. We used uncertainty analyses to model vaccines with four characteristics: (i) take, (ii) duration of immunity, (iii) reduction in transmissibility/fitness, and (iv) increase in survival. We reconstructed, and forecasted, the South African epidemic from 1940 to 2140 (assuming no vaccination). We predict that: (i) incidence will peak in 2014, decline, and stabilize, (ii) prevalence will continue to rise, and (iii) the AIDS death rate curve will peak in 2022. Our predictions show that (over the next 135 years) the epidemic in South Africa will switch from a predominantly Subtype C epidemic to an epidemic driven by other subtypes. We predict that the epidemic could remain unchanged, even with mass vaccination with a vaccine that is equally effective against all co-circulating subtypes. However, if the non-C subtypes are less (or equally) transmissible as Subtype C then disease-modifying vaccines could result in eradication. Thus, in countries where multiple-subtypes are co-circulating it is critical to realize that small biological differences among subtypes will have dramatic consequences for the effectiveness of HIV vaccination campaigns. A slight difference in fitness will determine whether a disease-modifying vaccine has almost no impact on the epidemic or can achieve eradication.