The genus Clostridium comprises a heterogeneous group of organisms for which the phylogeny and evolutionary relationships are poorly understood. The elucidation of these evolutionary relationships necessitates the use of experimental methods that can distinguish Clostridium lineages that are time and cost effective, and can be accurately and reproducibly employed in different laboratories. Multi-locus sequence typing (MLST) has been successfully used as a reproducible and discriminating system in the study of eukaryotic and prokaryotic evolutionary biology, and for strain typing of various bacteria. In this study, MLST was applied to evaluate the evolutionary lineages in the serotype A group of Clostridium botulinum. C. botulinum type A has recently been shown to produce multiple subtypes, suggesting that it is not monophyletic as previously reported, but comprises distinct lineages. For MLST analysis, we initially evaluated 14 housekeeping genes (gapdh, tuf, sod, oppB, hsp60, dnaE, aroE, pta, 23S rDNA, aceK, rpoB, 16S rDNA, mdh and recA) for amplification and sequence analysis. In the first phase of the analysis, 30 C. botulinum type A strains producing botulinum neurotoxin subtypes A1-A4 were examined. Results of this pilot study suggested that seven of the genes (mdh, aceK, rpoB, aroE, hsp60, oppB and recA) could be used for elucidation of evolutionary lineages and strain typing. These seven housekeeping genes were successfully applied for the elucidation of lineages for 73 C. botulinum type A strains, which resulted in 24 distinct sequence types. This strategy should be applicable to phylogenetic studies and typing of other C. botulinum serotypes and Clostridium species.