Lupinus is known to form endophytic associations with both nodulating and non-nodulating bacteria. In this study, multilocus sequence analysis (MLSA) was used to analyze phylogenetic relationships among root nodule bacteria associated with Lupinus and soybean. Out of 17 bacterial strains analyzed, 13 strains isolated from root nodules of Lupinus spp. were obtained from the National Rhizobium Germplasm Resource Collection, USDA. Additionally, two strains of root-nodule bacteria isolated each from native lupinus and domestic soybean were examined. Sequences of the 16S rRNA gene and three house-keeping genes (atpD, dnaK and glnII) were used. All the reference genes were retrieved from the existing complete genome sequences only. The clustering of 12 of the strains was consistent among single and concatenated gene trees, but not USDA strains 3044, 3048, 3504, 3715, and 3060. According to the concatenated phylogeny, we suggest that USDA 3040, 3042, 3044, 3048, 3051, 3060, 3504, 3709 and 3715 are Bradyrhizobium, USDA 3063 and 3717 are Mesorhizobium, USDA 3043 is Burkholderia and USDA 3057a is Microvirga. The two strains isolated from native lupines in this study are Burkholderia and Rhizobium, whereas the two from domestic soybean are Bradyrhizobium. This study emphasizes the robustness of MLSA, the diversity of bacterial species that are capable of nodulating lupine and the substantial capability of Burkholderia spp. to colonize lupine root nodules.