The diversity of BoNT-producing Clostridia is still a worrying problem for specialists who explore the evolutionary and taxonomic diversity of C. botulinum. It is also a problem for epidemiologists and laboratory staff conducting investigations into foodborne botulism in humans and animals, because their genetic and phenotypic heterogeneity cause complications in choosing the proper analytical tools and in reliably interpreting results. Botulinum neurotoxins (BoNTs) are produced by several bacterial groups that meet all the criteria of distinct species. Despite this, the historical designation of C. botulinum as the one species that produces botulinum toxins is still exploited. New genetic tools such as whole-genome sequencing (WGS) indicate horizontal gene transfer and the occurrence of botulinum gene clusters that are not limited only to Clostridium spp., but also to Gram-negative aerobic species. The literature data regarding the mentioned heterogeneity of BoNT-producing Clostridia indicate the requirement to reclassify C. botulinum species and other microorganisms able to produce BoNTs or possessing botulinum-like gene clusters. The aim of this study was to present the problem of the diversity of BoNT-producing Clostridia over time and new trends toward obtaining a reliable classification of these microorganisms, based on a complex review of the literature.