The impact of soil metal pollution on plant communities has been studied extensively in the past. However, very little is known about the fungal species that co-occur with these plant communities on metal polluted soils. We characterized the belowground fungal community in a heavy metal polluted and a non-polluted soil using 454 pyrosequencing. The fungal communities at both study sites were shown to consist mainly of the same ectomycorrhizal species, but a consistent shift in the relative abundances of these species was observed, whereas no differences in fungal diversity were found. In metal polluted soil, root tips of young pines were initially largely colonized by stress-tolerant dark Ascomycota that were mostly replaced by metal-tolerant Basidiomycota within 2 years. Compared to older forests, a low belowground fungal diversity was observed in the two pioneer stands.