The genus Lactobacillus contains over 80 recognized species, and is characterized by a high level of diversity, reflected in its complex phylogeny. The authors' recent determination of the genome sequence of Lactobacillus salivarius means that five complete genomes of Lactobacillus species are available for comparative genomics: L. salivarius, L. plantarum, L. acidophilus, L. johnsonii and L. sakei. This paper now shows that there is no extensive synteny of the genome sequences of these five lactobacilli. Phylogeny based on whole-genome alignments suggested that L. salivarius was closer to L. plantarum than to L. sakei, which was closest to Enterococcus faecalis, in contrast to 16S rRNA gene relatedness. A total of 593 orthologues common to all five species were identified. Species relatedness based on this protein set was largely concordant with genome synteny-based relatedness. A Lactobacillus supertree, combining individual phylogenetic trees from each of 354 core proteins, had four main branches, comprising L. salivarius-L. plantarum; L. sakei; E. faecalis; and L. acidophilus-L. johnsonii. The extreme divergence of the Lactobacillus genomes analysed supports the recognition of new subgeneric divisions.