We investigated the genetic diversity of measles virus (MV) in Nigeria (2004–2005) and the Democratic Republic of the Congo (DRC)(2002–2006). Genotype B3 strains circulating in Kinshasa, DRC, in 2002–2003 were fully replaced by genotype B2 in 2004 at the end of the second Congo war. In Nigeria (2004–2005), two genetic clusters of genotype B3, both of which were most closely related to 1 variant from 1998, were identified. Longitudinal analysis of MV strain diversity in Nigeria suggested that only a few of the previously described 1997–1998 variants had continued to circulate, but this finding was concomitant with a rapid restoration of genetic diversity, probably caused by low vaccination coverage and high birth rates. In contrast, the relatively low genetic diversity of MV in DRC and the genotype replacement in Kinshasa reflect a notable improvement in local measles control.