We analyzed the diversity and identity of the rhizobial populations nodulating an invasive Australian legume tree Acacia mearnsii in a natural Quercus suber forest in the El Kala National Park, Algeria. Soils from three different forest plots corresponding to non invaded original Q. suber stand, partially invaded by A. mearnsii, and totally invaded (monodominant) A. mearnsii stand were used to trap nodulating bacteria with the same tree species. Symbiotic nitrogen-fixing bacteria were isolated from root nodules and characterized by sequencing of the internal transcribed spacer region, then submitted to phylogenetic analyses. A total of 67 isolates was obtained, representing the 3 different forest plots, all renodulating A. mearnsii in monoxenic conditions. Phylogenetic analyses showed that all isolates belong to different Bradyrhizobium lineages, according to each of the three locations with little intermixing between forest plots. These results illustrate the adaptation of nodulating Bradyrhizobium populations to the new soil conditions induced by invasion. This symbiotic adaptability is presumed to be a key factor of the invasive character of this tree species.