Soybean inoculation with effective rhizobial strains makes unnecessary the use of N-fertilizers in the tropics. A frequently reported problem is the failure of the inoculant strains to overcome the competition imposed by indigenous rhizobial populations. The screening of indigenous rhizobia, already adapted to local conditions, searching for highly effective strains for use as inoculants represents a promising strategy in overcoming inoculation failure. The objective of this study was to isolate and characterize indigenous rhizobia and to identify strains that hold potential to be included in inoculant formulations for soybean production, with both promiscuous and non-promiscuous soybean cultivars, in Mozambican agro-climatic conditions. A total of 105 isolates obtained from nodules of promiscuous soybean grown at 15 sites were screened for N2-fixation effectiveness in the greenhouse along with five commercial strains. Eighty-seven isolates confirmed the ability to form effective nodules on soybean and were used for genetic characterization by rep-PCR (BOX) and sequencing of the 16S rRNA gene, and also for symbiotic effectiveness. BOX-PCR fingerprinting revealed remarkable genetic diversity, with 41 clusters formed, considering a similarity level of 65%. The 16S rRNA analysis assigned the isolates to the genera Bradyrhizobium (75%) and Agrobacterium/Rhizobium (25%). Great variability in symbiotic effectiveness was detected among the indigenous rhizobia from Mozambique, with ten isolates performing better than the commercial strain B. diazoefficiens USDA 110, the best reference strain, and 51 isolates with lower performance than all reference strains. Thirteen of the best isolates from the first greenhouse trial were evaluated, along with the five commercial strains, in two promiscuous (TGx 1963-3F and TGx 1835-10E) and one non-promiscuous (BRS 284) soybean cultivars in a second greenhouse trial. In general the promiscous soybeans responded better to inoculation. The 13 isolates were also characterized for tolerance to acidity and alkalinity (pH 3.5 and 9.0, respectively), salinity (0.1, 0.3 and 0.5 mol L−1 of NaCl) and high temperatures (35, 40 and 45 °C) in vitro. Five isolates, three (Moz 4, Moz 19 and Moz 22) belonging to the superclade B. elkanii and two (Moz 27 and Moz 61) assigned to the superclade B. japonicum, consistently showed high symbiotic effectiveness, suggesting that the inoculation with indigenous rhizobia adapted to local conditions represents a possible strategy for increasing soybean yields in Mozambique. Phylogenetic position of the five elite isolates was confirmed by the MLSA with four protein-coding housekeeping genes, dnaK, glnII, gyrB and recA.