Although legume biodiversity is concentrated in tropical regions, the majority of studies on legume nodulating bacteria (LNB) are focused on cultivated leguminous plants from temperate regions. However, recent works on tropical regions tend to indicate that the actual diversity of LNB is largely underestimated. In this study, we report the isolation and characterization of 68 nitrogen-fixing root nodule bacteria collected from eight endemic tree species of Dalbergia in Madagascar. The isolates were characterized by (i) restriction fragment length polymorphism (RFLP) analysis of 16S-IGS rDNA, (ii) 16S rDNA gene sequencing and (iii) nodulation tests. Results revealed a wide diversity of bacteria present in the nodules of Dalbergia. Among the 68 isolated bacteria, 65 belonged to Bradyrhizobium, Mesorhizobium, Rhizobium, Azorhizobium and Phyllobacterium from the alpha-class of Proteobacteria, and three isolates belonged to Burkholderia and Ralstonia from the beta-class of Proteobacteria. Our results also show for the first time that a strain belonging to the Burkholderia cepacia complex is able to induce efficient nodules on a legume plant.