Numerous epidemiological studies from the early years of the tragic HIV and AIDS pandemic in sub-Saharan Africa identified formal education as a risk factor increasing the chance of infection. Instead of playing its usual role as a preventative factor, as has been noted in many other public health cases, until the mid-1990s educated African men and women had a higher risk of contracting HIV than their less educated peers. This led to ambivalent policy about the efficacy of education as a possible social vaccine against new infections in this region. Reported here is a cohort analysis of formal education and HIV infection in 11 African countries showing that among younger adults, who came to sexual maturity after widespread misconceptions and misinformation about the causes of the disease were reduced, more schooling is associated with a lower risk of HIV infection. The results are discussed in light of a critique of past weak hypotheses about how education works as a social vaccine, and a new hypothesis is developed. Policy implications are described for renewed efforts towards the supply of quality education as an important strategy to promote public health in sub-Saharan Africa.