Evolutionary relationships of 120 root-nodulating bacteria isolated from the nodules of Pisum sativum cultivated at 22 different locations of the trans-Himalayan valleys of Lahaul and Spiti in the state of Himachal Pradesh of India were studied using 16S rRNA gene PCR-RFLP, ERIC-PCR, sequencing of 16S rRNA, atpD, recA, nodC and nifH genes, carbon-source utilization pattern (BIOLOG™), and whole-cell fatty acid profiling. The results demonstrated that all isolates belonged to Rhizobium leguminosarum symbiovar viciae (Rlv). Isolates from the two valleys were clearly separated on the basis of ERIC fingerprints, carbon-source utilization pattern, and whole-cell fatty acid methyl esters. Phylogenetic analysis of atpD, recA, nodC and nifH genes revealed a common Rlv sublineage in Spiti valley. Lahaul valley isolates were represented by 3 sequence types of atpD and recA genes, and four sequence types of nodC and nifH genes. Genotypes from the two valleys were completely distinct, except for two Lahaul isolates that shared nodC and nifH sequences with Spiti isolates but were otherwise more similar to other Lahaul isolates. Isolates from the two highest Spiti valley sites (above 4000m) had a distinctive whole-cell fatty acid profile. Spiti valley isolates are closely related to Rlv sublineages from Xinjiang and Shanxi provinces in China, while Lahaul valley isolates resemble cosmopolitan strains of the western world. The high mountain pass between these valleys represents a boundary between two distinct microbial populations.