As the main source of inocula, ectomycorrhizal (ECM) fungal propagules are critical for root colonization and seedling survival in deforested areas. It is essential to know factors that may affect the diversity and composition of ECM fungal community on roots of seedlings planted in deforest areas during reforestation. We quantitatively evaluated the effect of host plant and soil origin on ECM fungal propagule community structure established on roots of Castanopsis fargesii, Lithocarpus harlandii, Pinus armandii, and Pinus massoniana growing in soils from local natural forests and from sites deforested by clear-cut logging in the 1950s and 1960s. ECM root tips were sampled in April, July, and October of 2006, and ECM fungal communities were determined using ECM root morphotyping, internal transcribed spacer (ITS)-RFLP, and ITS sequencing. A total of 36 ECM fungal species were observed in our study, and species richness varied with host species and soil origin. Decreased colonization rates were found in all host species except for L. harlandii, and reduced species richness was found in all host species except for P. armandii in soil from the deforested site, which implied the great changes in ECM fungal community composition. Our results showed that 33.3% variance in ECM fungal community composition could be explained by host plant species and 4.6% by soil origin. Results of indicator species analysis demonstrated that 14 out of 19 common ECM fungal species showed significant preference to host plant species, suggesting that the host preference of ECM fungi was one of the most important mechanisms in structuring ECM fungal community. Accordingly, the host plant species should be taken into account in the reforestation of deforested areas due to the strong and commonly existed host preference of ECM fungi.