The colonization of terrestrial environments by rooted vascular plants had far-reaching impacts on the Earth system. However, the belowground structures of early vascular plants are rarely documented, and thus the plant−soil interactions in early terrestrial ecosystems are poorly understood. Here we report the earliest rooted paleosols (fossil soils) in Asia from Early Devonian deposits of Yunnan, China. Plant traces are extensive within the soil and occur as complex network-like structures, which are interpreted as representing long-lived, belowground rhizomes of the basal lycopsid Drepanophycus. The rhizomes produced large clones and helped the plant survive frequent sediment burial in well-drained soils within a seasonal wet−dry climate zone. Rhizome networks contributed to the accumulation and pedogenesis of floodplain sediments and increased the soil stabilizing effects of early plants. Predating the appearance of trees with deep roots in the Middle Devonian, plant rhizomes have long functioned in the belowground soil ecosystem. This study presents strong, direct evidence for plant−soil interactions at an early stage of vascular plant radiation. Soil stabilization by complex rhizome systems was apparently widespread, and contributed to landscape modification at an earlier time than had been appreciated.