The remediation of metal-contaminated soils by phytoextraction depends on plant growth and plant metal accessibility. Soil microorganisms can affect the accumulation of metals by plants either by directly or indirectly stimulating plant growth and activity or by (im)mobilizing and/or complexing metals. Understanding the intricate interplay of metal-accumulating plants with their rhizosphere microbiome is an important step toward the application and optimization of phytoremediation. We compared the effects of a "native" and a strongly disturbed (gamma-irradiated) soil microbial communities on cadmium and zinc accumulation by the plant Arabidopsis halleri in soil microcosm experiments. A. halleri accumulated 100% more cadmium and 15% more zinc when grown on the untreated than on the gamma-irradiated soil. Gamma irradiation affected neither plant growth nor the 1MHCl-extractable metal content of the soil. However, it strongly altered the soil microbial community composition and overall cell numbers. Pyrosequencing of 16S rRNA gene amplicons of DNA extracted from rhizosphere samples of A. halleri identified microbial taxa (Lysobacter, Streptomyces, Agromyces, Nitrospira, "Candidatus Chloracidobacterium") of higher relative sequence abundance in the rhizospheres of A. halleri plants grown on untreated than on gamma-irradiated soil, leading to hypotheses on their potential effect on plant metal uptake. However, further experimental evidence is required, and wherefore we discuss different mechanisms of interaction of A. halleri with its rhizosphere microbiome that might have directly or indirectly affected plant metal accumulation. Deciphering the complex interactions between A. halleri and individual microbial taxa will help to further develop soil metal phytoextraction as an efficient and sustainable remediation strategy.