Few sub-Saharan African countries have witnessed declines in HIV prevalence, and only Uganda has compelling evidence for a decline founded on sexual behavior change. We report a decline in HIV prevalence in eastern Zimbabwe between 1998 and 2003 associated with sexual behavior change in four distinct socioeconomic strata. HIV prevalence fell most steeply at young ages—by 23 and 49%, respectively, among men aged 17 to 29 years and women aged 15 to 24 years—and in more educated groups. Sexually experienced men and women reported reductions in casual sex of 49 and 22%, respectively, whereas recent cohorts reported delayed sexual debut. Selective AIDS-induced mortality contributed to the decline in HIV prevalence.