Rhizobia, bacteria that fix atmospheric nitrogen, are important agricultural resources. In order to establish the evolutionary relationships among rhizobia isolated from different geographic regions and different plant hosts for systematic studies, we evaluated the use of physical structure of the rhizobial genomes as a phylogenetic marker to categorize these bacteria. In this work, we analyzed the features of genome structures of 64 rhizobial strains. These rhizobial strains were divided into 21 phylogenetic clusters according to the features of genome structures evaluated by the endonuclease I-CeuI. These clusters were supported by 16S rRNA comparisons and genomic sequences of four rhizobial strains, but they are largely different from those based on the current taxonomic scheme (except 16S rRNA).