The legume-rhizobium association is widely used around the world to improve crop production via nitrogen fixation (N2-fixation). Inoculation with suitable strains is required in order to establish effective symbioses in soils. Plant growth-promoting rhizobacteria (PGPR) are of biotechnological interest since they can improve plant health and soil fertility. A collection of root-nodulating bacteria was isolated from Leucaena leucocephala in the Yucatan Peninsula in Mexico. The isolates were characterized based on their phenotypic features including growth rate, acidification in culture media, utilization of carbon sources and salinity stress tolerance. The antibiotic resistance level of selected strains was tested against five different antibiotics and showed that most of the strains were sensitive to kanamycin (30 µg) but resistant to ampicillin (10 µg)and trimethoprim/sulfamethoxazole (1.25/23.75 μg). Isolates 40a and 74 produced substantial amounts of indole-3-acetic acid (IAA), and other isolates produced siderophores. These isolates were used to verify their nodulation capacity on L. leucocephala. The 16S rRNA gene products were sequenced to determine the identity and phylogenetic diversity of the isolates, placing them in the genera Rhizobium and Sinorhizobium (syn. Ensifer). Based on this study, we propose that isolates Sinorhizobium (40a) and Rhizobium (74) are potential candidates to be used as inoculants to enhance symbioses and N2-fixation using Leucaena leucocephala in karst soils.