Arbuscular mycorrhizal fungi (AMF) have been shown to play an important role in increasing plant fitness in harsh conditions. Therefore, AMF are currently considered to be effective partners in phytoremediation. However, AMF communities in high levels of petroleum pollution are still poorly studied. We investigated the community structures of AMF in roots and rhizospheric soils of two plant species, Eleocharis elliptica and Populus tremuloides, growing spontaneously in high petroleum-contaminated sedimentation basins of a former petrochemical plant (91,000 μg/Kg of C10-C50 was recorded in a basin which is 26-fold higher than the threshold of polluted soil in Quebec, Canada). We used a PCR cloning, and sequencing approach, targeting the 18S rRNA gene to identify AMF taxa. The high concentration of petroleum-contamination largely influenced the AMF diversity, which resulted in less than five AMF operational taxonomical units (OTUs) per individual plant at all sites. The OTUs detected belong mainly to the Glomerales, with some from the Diversisporales and Paraglomerales, which were previously reported in high concentrations of metal contamination. Interestingly, we found a strong phylogenetic signal in OTU associations with host plant species identity, biotopes (roots or soils), and contamination concentrations (lowest, intermediate and highest). The genus Rhizophagus was the most dominant taxon representing 74.4% of all sequences analyzed in this study and showed clear association with the highest contamination level. The clear association of Rhizophagus with high contamination levels suggests the importance of the genus for the use of AMF in bioremediation, as well as for the survey of key AMF genes related to petroleum hydrocarbon resistance. By favoring plant fitness and mediating its soil microbial interactions, Rhizophagus spp. could enhance petroleum hydrocarbon pollutant degradation by both plants and their microbiota in contaminated sites.