Using high throughput sequencing of the nodA gene, we studied the population dynamics of Rhizobium leguminosarum (bv. viciae, bv. trifolii) in rhizospheric and nodular subpopulations associated with the leguminous plants representing different cross-inoculation groups (Vicia sativa, Lathyrus pratensis of the vetch/vetchling/pea group and Trifolium hybridum of the clover group). The “rhizosphere → nodules” transitions result in either an increase or decrease in the frequencies of 10 of the 23 operational taxonomic units (OTUs) (which were identified with 95% similarity) depending on the symbiotic specificity and phylogenetic positions of OTUs. Statistical and bioinformatical analysis of the population structures suggest that the type of natural selection responsible for these changes may be diversifying at the whole-population level and frequency-dependent at the OTU-specific level, ensuring the divergent evolution of rhizobia interacting with different host species.