The genetic structures of bacterial communities associated with Medicago truncatula Gaertn. cv. Jemalong line J5 (Myc+ Nod+) and its symbiosis-defective mutants TRV48 (Myc+ Nod–) and TRV25 (Myc– Nod–) were compared. Plants were cultivated in a fertile soil (Châteaurenard, France) and in soil from the Mediterranean basin showing a low fertility (Mas d'Imbert, France). Plant growth, root architecture, and the efficiency of root symbiosis of the three plant genotypes were characterized in the two soils. Structures of the bacterial communities were assessed by automated-ribosomal intergenic spacer analysis (A-RISA) fingerprinting from DNA extracted from the rhizosphere soil and root tissues. As expected, the TRV25 mutant did not develop endomycorrhizal symbiosis in any of the soils, whereas mycorrhization of line J5 and the TRV48 mutant occurred in both soils but at a higher intensity in the Mas d'Imbert (low fertility) than in the Châteaurenard soil. However, modifications of plant growth and root architecture, between mycorrhizal (J5 and TRV48) and nonmycorrhizal (TRV25) plants, were recorded only when cultivated in the Mas d'Imbert soil. Similarly, the genetic structures of bacterial communities associated with mycorrhizal and nonmycorrhizal plants differed significantly in the Mas d'Imbert soil but not in the Châteaurenard soil. Multivariate analysis of the patterns allowed the identification of molecular markers, explaining these differences, and markers were further sequenced. Molecular marker analysis allowed the delineation of 211 operational taxonomic units. Some of those belonging to the Comamonadaceae and Oxalobacteraceae (ß-Proteobacteria) families were found to be significantly more represented within bacterial communities associated with the J5 line and the TRV48 mutant than within those associated with the TRV25 mutant, indicating that these bacterial genera were preferentially associated with mycorrhizal roots in the Mas d'Imbert soil.