Little is known regarding how the increased diversity of nitrogen-fixing bacteria contributes to the productivity and diversity of plants in complex communities. However, some authors have shown that the presence of a diverse group of nodulating bacteria is required for different plant species to coexist. A better understanding of the plant symbiotic organism diversity role in natural ecosystems can be extremely useful to define recovery strategies of environments that were degraded by human activities. This study used ARDRA, BOX-PCR fingerprinting and sequencing of the 16S rDNA gene to assess the diversity of root nodule nitrogen-fixing bacteria in former bauxite mining areas that were replanted in 1981, 1985, 1993, 1998, 2004 and 2006 and in a native forest. Among the 12 isolates for which the 16S rDNA gene was partially sequenced, eight, three and one isolate(s) presented similarity with sequences of the genera Bradyrhizobium, Rhizobium and Mesorhizobium, respectively. The richness, Shannon and evenness indices were the highest in the area that was replanted the earliest (1981) and the lowest in the area that was replanted most recently (2006).