Abstract Rhizobia nodulating native Astragalus and Oxytropis spp. in Northern Europe are not well-studied. In this study, we isolated bacteria from nodules of four Astragalus spp. and two Oxytropis spp. from the arctic and subarctic regions of Sweden and Russia. The phylogenetic analyses were performed by using sequences of three housekeeping genes (16S rRNA, rpoB and recA) and two accessory genes (nodC and nifH). The results of our multilocus sequence analysis (MLSA) of the three housekeeping genes tree showed that all the 13 isolates belonged to the genus Mesorhizobium and were positioned in six clades. Our concatenated housekeeping gene tree also suggested that the isolates nodulating Astragalus inopinatus, Astragalus frigidus, Astragalus alpinus ssp. alpinus and Oxytropis revoluta might be designated as four new Mesorhizobium species. The 13 isolates were grouped in three clades in the nodC and nifH trees. 15N analysis suggested that the legumes in association with these isolates were actively fixing nitrogen.