The extremely diverse genus Lactobacillus is the largest among the lactic acid bacteria, with over 145 recognized species. In this work, which to our knowledge is the largest comparative phylogenomics study of a single genus to date, 12 genomes of Lactobacillus strains were subjected to an array of whole-genome and single-marker phylogenetic approaches, to investigate the case for extracting subgeneric groups and to determine whether a single congruent phylogeny could be identified. We conclude that GroEL is a more robust single-gene phylogenetic marker for the genus Lactobacillus than the 16S rRNA gene, when no whole-genome information is available. Significant incongruence was found, both within a set of trees based on 141 core proteins and within those phylogenies based on numbers of orthologues, concatenated RNA polymerase subunits and single gene/protein markers. This is possibly due to different evolutionary rates, hidden paralogies or horizontal gene transfer. Such phylogenetic ambiguities are efficiently visualized with cluster-networks. Although the genus contains some highly unstable taxa, four subgeneric groups were distinguished. Qualitative and quantitative gene analysis of these groups resulted in three findings: there is a relatively small number of group-specific proteins, the majority of which are poorly characterized; major groupings are functionally better distinguishable by absent genes rather than gained/retained genes; and, finally, a gene cluster possibly involved in purine metabolism is uniquely present in four lactobacilli associated with meat. In conclusion, because of either significantly different branching patterns or the availability of too few members, three of the four identified groups could not serve as the basis for identifying candidate novel genera within the current genus. We therefore suggest targeted sequencing of key taxonomic species identified here, which are likely to add sufficient depth for a future reclassification, followed by phylogenomic analysis involving the core proteins identified here. This will ideally be combined with phenotypic data using a polyphasic approach.