The genus includes over 200 species that are widely used in fermented food preservation and biotechnology or that are explored for beneficial effects on health. Naming, classifying, and comparing lactobacilli have been challenging due to the high level of phenotypic and genotypic diversity that they display and because of the uncertain degree of relatedness between them and associated genera. The aim of this study was to investigate the feasibility of dividing the genus into more homogeneous genera/clusters, exploiting genome-based data. The relatedness of 269 species belonging primarily to the families and was investigated through phylogenetic analysis (by the use of ribosomal proteins and housekeeping genes) and the assessment of the average amino acid identity (AAI) and the percentage of conserved proteins (POCP). For each subgeneric group that emerged, conserved signature genes were identified. Both distance-based and sequence-based metrics showed that the genus was paraphyletic and revealed the presence of 10 methodologically consistent subclades, which were also characterized by a distinct distribution of conserved signature orthologues. We present two ways to reclassify lactobacilli: a conservative division into two subgeneric groups based on the presence/absence of a key carbohydrate utilization gene or a more radical subdivision into 10 groups that satisfy more stringent criteria for genomic relatedness. Lactobacilli have significant scientific and economic value, but their extraordinary diversity means that they are not robustly classified. The 10 homogeneous genera/subgeneric entities that we identify here are characterized by uniform patterns of the presence/absence of specific sets of genes which offer potential as discovery tools for understanding differential biological features. Reclassification/subdivision of the genus into more uniform taxonomic nuclei will also provide accurate molecular markers that will be enabling for regulatory approval applications. Reclassification will facilitate scientific communication related to lactobacilli and prevent misidentification issues, which are still the major cause of mislabeling of probiotic and food products reported worldwide.