Soil fungi can help enhance ecosystem restoration, yet our understanding of how they reassemble on degraded lands is limited. Here we studied fungal community and network structure using DNA metabarcoding in forest restoration sites following agricultural abandonment and overgrazing in Japan. We used a natural experimental setting where reforestation with different numbers of tree species and deer exclusion is being conducted. We found that the mean fungal richness was 1.9 to 2.9-times higher in reforested stands than natural forests, regardless of the number of tree species planted. The degree of compositional dissimilarity among sites (beta diversity) was significantly lower in reforested stands than natural forests. These results were attributable to lower environmental heterogeneity, stronger dispersal limitation, and shorter time since the onset of community assembly in reforested stands than natural forests. Deer exclosure had neither sole nor interactive effects with reforestation on fungal community structure. The fungal co-occurrence network showed a highly-compartmentalized structure with distinct modules. Overall, the legacy of past agriculture and herbivory in fungal community structure appear to persist for decades even under proactive restoration of aboveground vegetation. Direct human interventions belowground are thus encouraged for the recovery of soil biota, which may, in turn, facilitate ecosystem restoration.