The aim of this work is to describe the diversity of potentially symbiotic bacteria associated with the invasive introduced legume Robinia pseudoacacia in China. Thirty-three isolates from 33 separate trees and nodules were characterized using restriction length fragment polymorphism and sequencing of 16S rRNA, nodA, nodC and nifH genes. Their 16S rRNA gene patterns and sequences placed them in three clades: 85% of isolates were related to the Mesorhizobium mediterraneum/ temperatum group, whereas the remaining were similar either to Mesorhizobium amorphae or to Sinorhizobium meliloti. However, despite their diverse taxonomic positions, the nodA, nodC and nifH genes' phylogenies indicated that these R. pseudoacacia symbionts share similar symbiosis genes, implying gene transfers and a degree of host specificity. Comparison of R. pseudoacacia symbiotic diversity in native and other invaded areas suggests that most Chinese symbionts may not have arrived with the seed but were local bacteria that acquired specific symbiotic genes from native American rhizobia.