Thirty-two bacterial isolates were obtained from root nodules of Lupinus angustifolius growing in Northern Tunisia. Phylogenetic analyses based on recA and gyrB partial gene sequences grouped the strains into six clusters: four clusters belonged to the genus Bradyrhizobium (22 isolates), one to Microvirga (8 isolates) and one to Devosia (2 isolates), a genus that has not been previously reported to nodulate lupin. Representative strains of each group were further characterized. Multi-Locus Sequence Analysis (MLSA) based on recA and glnII gene sequences separated the strains within the genus Bradyrhizobium into four divergent clusters related to B. canariense, B. liaoningense, B. lupini, and B. algeriense, respectively. The latter might constitute a new Bradyrhizobium species. The strains in the Microvirga cluster showed high identity with M. tunisiensis. The Devosia isolates might also represent a new species within this genus. An additional phylogenetic analysis based on the symbiotic gene nodC affiliated the strains to symbiovars genistearum, mediterranense, and to a possibly new symbiovar. These results altogether contributed to the existing knowledge on the genetic diversity of lupin-nodulating microsymbionts and revealed a likely new, fast-growing, salt-tolerant rhizobial species within the genus Devosia as a potentially useful inoculant in agricultural practices or landscape restoration.