Aims To identify the rhizobia nodulating Vicia sativa in Northwestern China and to estimate their geographic distribution. Methods Rhizobia trapped with V. sativa plants from soils at six sites in the northwest of China were classified into genotypes by PCR-based restriction fragment length polymorphism (RFLP) of 16S-23S rRNA intergenic spacer (IGS) and 16S rRNA genes, and phylogenetic analyses of housekeeping (16S rRNA, recA, atpD) and symbiotic genes were performed for the representative strains. Soil physicochemical characteristics were recorded and canonical correlation analysis was performed to examine the correlations between soil features and distribution of rhizobial genotypes. Results A total of 202 rhizobial isolates were discriminated by RFLP analyses into 15 IGS types and a single 16S rRNA type, which were identified as Rhizobium by 16S rRNA gene phylogeny and as four clusters by multilocus sequence analysis (MLSA). Cluster 1 covering 86 strains and 7 IGS types prevalent in all sites was identified as Rhizobium laguerreae; cluster 2 was R. sophorae with 18 strains in 2 IGS types found in the site Q-GD. Each of cluster 3 and cluster 4 contained three IGS types representing two novel Rhizobium genospecies specific to Gansu Province and Shanxi Province, respectively. Four nodC phylogenetic clades were defined among the isolates. Conclusions R. sophorae, R. laguerreae, and two novel Rhizobium genospecies with diverse symbiotic genotypes are associated with Vicia sativa L. in Northwest China. Their biogeographic patterns are mainly directed by soil pH and salinity. This is the first study on the diversity of rhizobia nodulating Vicia sativa in China.