Leuconostocis a genus of saccharolytic heterofermentative lactic acid bacteria that inhabit plant-derived matrices and a variety of fermented foods (dairy products, dough, milk, vegetables, and meats), contributing to desired fermentation processes or playing a role in food spoilage. At present, the genus encompasses 17 recognized species. In total, 216 deposited genome sequences ofLeuconostocwere analyzed, to check the delineation of species and to infer their evolutive genealogy utilizing a minimum evolution tree of Average Nucleotide Identity (ANI) and the core genome alignment. Phylogenomic relationships were compared to those obtained from the analysis of 16S rRNA,pheS, andrpoAgenes. All the phylograms were subjected to split decomposition analysis and their topologies were compared to check the ambiguities in the inferred phylogenesis. The minimum evolution ANI tree exhibited the most similar topology with the core genome tree, while single gene trees were less adherent and provided a weaker phylogenetic signal. In particular, the 16S rRNA gene failed to resolve several bifurcations andLeuconostocspecies. Based on an ANI threshold of 95%, the organization of the genusLeuconostoccould be amended, redefining the boundaries of the speciesL. inhae, L. falkenbergense, L. gelidum, L. lactis, L. mesenteroides, andL. pseudomesenteroides. Two strains currently recognized asL. mesenteroideswere split into a separate lineage representing a putative species (G16), phylogenetically related to bothL. mesenteroides(G18) andL. suionicum(G17). Differences among the four subspecies ofL. mesenteroideswere not pinpointed by ANI or by the conserved genes. The strains ofL. pseudomesenteroideswere ascribed to two putative species, G13 and G14, the former including also all the strains presently belonging toL. falkenbergense. L. lactiswas split into two phylogenetically related lineages, G9 and G10, putatively corresponding to separate species and both including subgroups that may correspond to subspecies. The speciesL. gelidumandL. gasicomitatumwere closely related but separated into different species, the latter including alsoL. inhaestrains. These results, integrating information of ANI, core genome, and housekeeping genes, complemented the taxonomic delineation with solid information on the phylogenetic lineages evolved within the genusLeuconostoc.