We study the relationship between education and HIV status using nationally representative data from 39 Demographic and Health Surveys (DHS) in Sub-Saharan Africa. First, we construct an innovative algorithm that systematically defines aggregate stages of the HIV epidemic in a comparable manner across time and across space. Second, we exploit the variation in the aggregate HIV stages in the DHS data, and find that the education gradient in HIV shows a U-shaped (positive-zero-positive) pattern over the course of the epidemic. Further, educational disparities in the number of extramarital partners are largely consistent with the evolution of the education gradient in HIV.