We analyzed temporal changes in the frequencies of the ptxA, prn, fim2, and fim3 alleles in Bordetella pertussis strains isolated from pertussis patients in Moscow, Russia, from 1948 to 2004. The three strains used for the whole-cell vaccine harbored the alleles ptxA2, ptxA4, prn1, fim2-1, and fim3A. Vaccine-type alleles of ptxA (ptxA2 and ptxA4) were characteristic for all prevaccination strains and for 96% of the strains isolated in the 1960s and 1970s. At the beginning of the 1970s, ptxA2 and ptxA4 were replaced by the ptxA1 allele. In the 1980s and to the present, strains with ptxA1 were predominant in the B. pertussis population. All prevaccination strains harbored the prn1 allele, which corresponds to the vaccine-type allele. In subsequent years, the proportion of strains with the prn1 allele decreased and the proportion of prn3 and prn2 strains increased. From 2002 to 2004 strains with prn2 or prn3 were predominant in the B. pertussis population. The vaccine-type alleles fim2-1 and fim3A were found in all prevaccination strains and in 92% of the strains isolated from 1960 to 1989. The fim2-2 and fim3B alleles were first observed at the beginning of the 1980s. In subsequent years, these strains became predominant. Together with waning immunity, the antigenic divergence between vaccine strains and clinical isolates observed in the Moscow area may explain the persistence of pertussis, despite the high rates of vaccine coverage. The results demonstrate that the selection of B. pertussis strains for vaccine manufacturing must be based on a thorough study of the B. pertussis population.