Abstract Erythrina velutina ("mulungu") is a legume tree from Caatinga that associates with rhizobia but the diversity and symbiotic ability of "mulungu" rhizobia are poorly understood. The aim of this study was to characterize "mulungu" rhizobia from Caatinga. Bacteria were obteined from Serra Talhada and Caruaru in Caatinga under natural regeneration. The bacteria were evaluated to the amplification of nifH and nodC and to metabolic characteristics. Ten selected bacteria identified by 16S rRNA sequences. They were tested in vitro to NaCl and temperature tolerance, auxin production and calcium phosphate solubilization. The symbiotic ability were assessed in an greenhouse experiment. A total of 32 bacteria were obtained and 17 amplified both symbiotic genes. The bacteria showed a high variable metabolic profile. Bradyrhizobium (6), Rhizobium (3) and Paraburkholderia (1) were identified, differing from their geographic origin. The isolates grew up to 45 °C to 0.51 mol L-1 of NaCl. Bacteria which produced more auxin in the medium with l-tryptophan and two Rhizobium and one Bradyrhizobium were phosphate solubilizers. All bacteria nodulated and ESA 90 (Rhizobium sp.) plus ESA 96 (Paraburkholderia sp.) were more efficient symbiotically. Diverse and efficient rhizobia inhabit the soils of Caatinga dry forests, with the bacterial differentiation by the sampling sites.