Introducing nitrogen-fixing bacteria as an inoculum in association with legume crops is a common practice in agriculture. However, the question of the evolution of these introduced microorganisms remains crucial, both in terms of microbial ecology and agronomy. We explored this question by analyzing the genetic and symbiotic evolution of two Bradyrhizobium strains inoculated on Acacia mangium in Malaysia and Senegal 15 and 5 years, respectively, after their introduction. Based on typing of several loci, we showed that these two strains, although closely related and originally sampled in Australia, evolved differently. One strain was recovered in soil with the same five loci as the original isolate, whereas the symbiotic cluster of the other strain was detected with no trace of the three housekeeping genes of the original inoculum. Moreover, the nitrogen fixation efficiency was variable among these isolates (either recombinant or not), with significantly high, low, or similar efficiencies compared to the two original strains and no significant difference between recombinant and nonrecombinant isolates. These data suggested that 15 years after their introduction, nitrogen-fixing bacteria remain in the soil but that closely related inoculant strains may not evolve in the same way, either genetically or symbiotically. In a context of increasing agronomical use of microbial inoculants (for biological control, nitrogen fixation, or plant growth promotion), this result feeds the debate on the consequences associated with such practices.