European foulbrood (EFB) is a honey bee brood disease caused by the bacterium Melissococcus plutonius. Large-scale EFB outbreaks have been reported in several countries in recent decades, which entail costly sanitation measures of affected apiaries to restrict the spread of this contagious pathogen. To mitigate its impact, a better understanding of the population dynamics of the etiological agent is required. We here used multi-locus sequence typing (MLST) to infer the genetic diversity and geographical distribution of 160 M. plutonius isolates collected from EFB symptomatic honey bee colonies seven years apart. Isolates belonged to three clonal complexes (CCs) known worldwide and to 12 sequence types (STs), of which five were novel. Phylogenetic and clustering analyses showed that some of these novel sequence types have likely evolved locally during a period of outbreak, but most disappeared again. We further screened the isolates for melissotoxin A (mtxA), a putative virulence gene. The prevalence of STs in which mtxA was frequent increased over time, suggesting that this gene promotes spread. Despite the increased frequency of this gene in the population, the total number of cases decreased, which could be due to stricter control measures implemented before the second sampling period. Our results provide a better understanding of M. plutonius population dynamics and help identify knowledge gaps that limit efficient control of this emerging disease.