The soybean is an exotic plant introduced in Paraguay in this century; commercial cropping expanded after the 1970s. Inoculation is practiced in just 15 to 20% of the cropping areas, but root nodulation occurs in most sites where soybeans grow. Little is known about rhizobial diversity in South America, and no study has been performed in Paraguay until this time. Therefore, in this study, the molecular characterization of 78 rhizobial isolates from soybean root nodules, collected under field conditions in 16 sites located in the two main producing states, Alto Paraná and Itapúa, was undertaken. A high level of genetic diversity was detected by an ERIC-REP-PCR analysis, with the majority of the isolates representing unique strains. Most of the 58 isolates characterized by slow growth and alkaline reactions in a medium containing mannitol as a carbon source were clustered with strains representative of the Bradyrhizobium japonicum and Bradyrhizobium elkanii species, and the 16S ribosomal DNA (rDNA) sequences of 5 of those isolates confirmed the species identities. However, slow growers were highly polymorphic in relation to the reference strains, including five carried in commercial inoculants in neighboring countries, thus indicating that the Paraguayan isolates might represent native bradyrhizobia. Twenty isolates highly polymorphic in the ERIC-REP-PCR profiles were characterized by fast growth and acid reactions in vitro, and two of them showed high 16S rDNA identities with Rhizobium genomic species Q. However, two other fast growers showed high 16S rDNA identity with Agrobacterium spp., and both of these strains established efficient symbioses with soybean plants.