The studies of rhizobial diversity in the Phaseolus genus have focused on Phaseolus vulgaris. It is unclear how rhizobial diversity is associated with Phaseolus lunatus in areas where this legume is not native, such as Brazil. Therefore, we studied rhizobial diversity associated with P. lunatus bean in soils from Brazil. The study was conducted in a greenhouse, and seeds from each genotype of P. lunatus were sown in plastic bags containing soils originating from Northeast Brazil. The nodules used in isolation and characterization were collected at 45 days after seedling emergence. Fourteen isolates of rhizobia were obtained. DNA was extracted, and the 16S rRNA gene was sequenced using primers fD1 and rD1. More than half of the strains studied were positioned in the Bradyrhizobium clade (in the B. elkani superclade). One strain was positioned in the Rhizobium etli/Rhizobium phaseoli clade. Two strains were grouped within the R. tropici group. Three strains, ISOL16, ISOL21, and ISOL27, that may represent new lineages were found. According to our analysis of the partial sequence of the 16S rRNA gene of 14 rhizobia strains, there was high species diversity of rhizobia-nodulating P. lunatus in Northeast Brazil, including potential new species.