Bacterial associations with plant roots are thought to contribute to the success of phytoremediation. We tested the effect of addition of a polycyclic aromatic hydrocarbon contaminated soil on the structure of the rhizosphere microbial communities of wheat (Triticum aestivum), lettuce (Lactuca sativa var. Tango), zucchini (Cucurbita pepo spp. pepo var. Black Beauty), and pumpkin (C. pepo spp. pepo var. Howden) 16S rDNA terminal restriction fragment length polymorphism (T-RFLP) profiles of rhizosphere microbial communities from different soil/plant combinations were compared with a pairwise Pearson correlation coefficient. Rhizosphere microbial communities of zucchini and pumpkin grown in the media amended with highest degree of contaminated soil clustered separately, whereas communities of these plants grown in unamended or amended with lower concentrations of contaminated soil, grouped in a second cluster. Lettuce communities grouped similarly to cucurbits communities, whereas wheat communities did not display an obvious clustering. The variability of 16S rDNA T-RFLP profiles among the different plant/soil treatments were mostly due to the difference in relative abundance rather than presence/absence of T-RFLP fragments. Our results suggest that in highly contaminated soils, the rhizosphere microbial community structure is governed more by the degree of contamination rather than the plant host type.