We used multilocus variable-number tandem repeat analysis and multiple antigen sequence typing to characterize isolates of Bordetella pertussis strains circulating in Denmark during periods with and without pertussis vaccination coverage. Our results show substantial shifts in the B. pertussis population over time and a reduction in genetic diversity. These changes might have resulted from the introduction of pertussis vaccines in Denmark and other parts of Europe. The predominant strains currently circulating in Denmark resemble those in other European countries.