In tropical soils, diversity and biotechnological potential of symbiotic diazotrophic bacteria are high. However, the phylogenetic relationships of prominent strains are still poorly understood. In addition, in countries such as Brazil, despite the broad use of rhizobial inoculants, molecular methods are rarely used in the analysis of strains or determination of inoculant performance. In this study, both rep-PCR (BOX) fingerprintings and the DNA sequences of the 16S rRNA gene were obtained for 54 rhizobial strains officially authorized for the production of commercial inoculants in Brazil. BOX-PCR has proven to be a reliable fingerprinting tool, reinforcing the suggestion of its applicability to track rhizobial strains in culture collections and for quality control of commercial inoculants. On the other hand, the method is not adequate for grouping or defining species or even genera. Nine strains differed in more than 1.03% (15) nucleotides of the 16S rRNA gene in relation to the closest type strain, strongly indicative of new species. Those strains were distributed across the genera Burkholderia, Rhizobium, and Bradyrhizobium.