Cicer canariense is a wild chickpea that can be nodulated by Mesorhizobium strains belonging to nine different genomic groups or genospecies. In this study, multilocus sequence analysis (MLSA) of seven protein-coding genes, recA, glnII, dnaK, rpoB, gyrB, truA and thrA, was used to resolve the phylogenetic relationships and taxonomic affiliation of 27 representative strains from all the genotypes. Individual phylogenies were mostly congruent, although there were a few discrepancies. Some genes were more discriminative than others, but concatenation of the seven genes produced a robust phylogeny of the genus Mesorhizobium. MLSA gave good support for the taxonomic affiliations of most of the genomic groups to previously recognized species and delineated several potential new species. Five genospecies found in C. canariense nodules showed average nucleotide identity values for seven genes (ANIg7) of >96% and they could be assigned to previously described Mesorhizobium species. Two large closely related genomic groups had M. caraganae as the closest species and they shared ANIg7 values in the 94–95% range, suggesting that they could be different subspecies or sister species. The predominant genospecies represented a novel monophyletic lineage that was well resolved from all currently recognized species of Mesorhizobium, with the highest ANIg7 below 92%. Other single strains represented potential new species.