Phytoremediation is an attractive alternative to excavating and chemically treating contaminated soils. Certain plants can directly bioremediate by sequestering and/or transforming pollutants, but plants may also enhance bioremediation by promoting contaminant-degrading microorganisms in soils. In this study, we used high-throughput sequencing of bacterial 16S rRNA genes and the fungal internal transcribed spacer (ITS) region to compare the community composition of 66 soil samples from the rhizosphere of planted willows (Salix spp.) and six unplanted control samples at the site of a former petrochemical plant. The Bray-Curtis distance between bacterial communities across willow cultivars was significantly correlated with the distance between fungal communities in uncontaminated and moderately contaminated soils but not in highly contaminated (HC) soils (>2000 mg kg(-1) hydrocarbons). The mean dissimilarity between fungal, but not bacterial, communities from the rhizosphere of different cultivars increased substantially in the HC blocks. This divergence was partly related to high fungal sensitivity to hydrocarbon contaminants, as demonstrated by reduced Shannon diversity, but also to a stronger influence of willows on fungal communities. Abundance of the fungal class Pezizomycetes in HC soils was directly related to willow phylogeny, with Pezizomycetes dominating the rhizosphere of a monophyletic cluster of cultivars, while remaining in low relative abundance in other soils. This has implications for plant selection in phytoremediation, as fungal associations may affect the health of introduced plants and the success of co-inoculated microbial strains. An integrated understanding of the relationships between fungi, bacteria and plants will enable the design of treatments that specifically promote effective bioremediating communities.