Studying rhizobia in the root nodules of Sphaerophysa salsula (Pall.) DC in the northwest of China, we obtained five strains classified as genus Rhizobium on the basis of their 16S rRNA gene sequences. The sequence similarity of strain CCNWQTX14(T) with the most related species was 99.0%. Further phylogenetic analysis of housekeeping genes (recA and atpD) suggested the five strains comprised a novel lineage within Rhizobium. The nifH and nodD gene sequences of CCNWQTX14(T) were phylogenetically closely related with those of Sinorhizobium kummerowiae and R. sphaerophysae, respectively. The five strains isolated from different places were also distinct from related Rhizobium species using ERIC fingerprint profiles. The DNA-DNA hybridization value was 41.8% between CCNWQTX14(T) and Rhizobium sphaerophysae CCNWGS0238(T). Our novel strains were only able to form effective nodules on its original host Sphaerophysa salsula. Our data showed that the five Rhizobium strains formed a unique genomic species, for which a novel species Rhizobium helanshanense sp. nov. is proposed. The type strain is CCNWQTX14(T) (=ACCC 16237(T) =HAMBI 3083(T)).