Insights into the evolution of plant cell walls have important implications for comprehending these diverse and abundant biological structures. In order to understand the evolving structure-function relationships of the plant cell wall, it is imperative to trace the origin of its different components. The present study is focused on plant 1,4-β-xylan, tracing its evolutionary origin by genome and transcriptome mining followed by phylogenetic analysis, utilizing a large selection of plants and algae. It substantiates the findings by heterologous expression and biochemical characterization of a charophyte alga xylan synthase. Of the 12 known gene classes involved in 1,4-β-xylan formation, XYS1/IRX10 in plants, IRX7, IRX8, IRX9, IRX14 and GUX occurred for the first time in charophyte algae. An XYS1/IRX10 ortholog from Klebsormidium flaccidum, designated K. flaccidumXYLAN SYNTHASE-1 (KfXYS1), possesses 1,4-β-xylan synthase activity, and 1,4-β-xylan occurs in the K. flaccidum cell wall. These data suggest that plant 1,4-β-xylan originated in charophytes and shed light on the origin of one of the key cell wall innovations to occur in charophyte algae, facilitating terrestrialization and emergence of polysaccharide-based plant cell walls.