Thirty-three rhizobial strains isolated from the root nodules of Astragalus luteolus and Astragalus ernestii growing on the west plateau at two different altitudes in Sichuan province, China, were characterized by amplified rDNA restriction analysis (ARDRA), amplified fragment length polymorphism (AFLP), and by sequencing of rrs, glnA, glnII and nifH. The ARDRA analysis revealed considerable genomic diversity. In AFLP analysis, 20 of 33 Astragalus rhizobia formed three distinct clades, with others dispersed into different groups with the reference strains. Phylogenetic analysis of the rrs gene of six representative strains showed that the isolates were members of the genus Mesorhizobium. Three of the isolates formed a sister clade to Mesorhizobium loti and Mesorhizobium ciceri, whereas the other three formed a sister clade to a clade harboring the species Mesorhizobium huakuii, Mesorhizobium plurifarum, Mesorhizobium septentrionale and Mesorhizobium amorphae, indicating the existence of two new species. Phylogenetic analysis of glnA and glnII confirmed the rrs phylogenies for four strains, but the trees were incongruent. The nifH sequences of the strains formed a monophyletic clade and were typical of those of mesorhizobia forming symbioses with inverted repeat lacking clade legume species. The incongruent phylogenies of the genes studied suggest that horizontal gene transfer and recombination shape mesorhizobial populations in the gene center of the host plants.