Ten rhizobial strains were isolated from root nodules of a relict legume Oxytropis popoviana Peschkova. For identification of the isolates, sequencing of rrs, the internal transcribed spacer region, and housekeeping genes recA, glnII, and rpoB was used. Nine fast-growing isolates were Mesorhizobium-related; eight strains were identified as M. japonicum and one isolate belonged to M. kowhaii. The only slow-growing isolate was identified as a Bradyrhizobium sp. Two strains, M. japonicum Opo-242 and Bradyrhizobium sp. strain Opo-243, were isolated from the same nodule. Symbiotic genes of these isolates were searched throughout the whole-genome sequences. The common nodABC genes and other symbiotic genes required for plant nodulation and nitrogen fixation were present in the isolate Opo-242. Strain Opo-243 did not contain the principal nod, nif, and fix genes; however, five genes (nodP, nodQ, nifL, nolK, and noeL) affecting the specificity of plant-rhizobia interactions but absent in isolate Opo-242 were detected. Strain Opo-243 could not induce nodules but significantly accelerated the root nodule formation after coinoculation with isolate Opo-242. Thus, we demonstrated that taxonomically different strains of the archaic symbiotic system can be co-microsymbionts infecting the same nodule and promoting the nodulation process due to complementary sets of symbiotic genes.