Mixed-linkage (1,3;1,4)-β-glucan (MLG), an abundant cell wall polysaccharide in the Poaceae, has been detected in ascomycetes, algae, and seedless vascular plants, but not in eudicots. Although MLG has not been reported in bryophytes, a predicted glycosyltransferase from the moss Physcomitrella patens (Pp3c12_24670) is similar to a bona fide ascomycete MLG synthase. We tested whether Pp3c12_24670 encodes an MLG synthase by expressing it in wild tobacco (Nicotiana benthamiana) and testing for release of diagnostic oligosaccharides from the cell walls by either lichenase or (1,4)-β-glucan endohydrolase. Lichenase, an MLG-specific endohydrolase, showed no activity against cell walls from transformed N. benthamiana, but (1,4)-β-glucan endohydrolase released oligosaccharides that were distinct from oligosaccharides released from MLG by this enzyme. Further analysis revealed that these oligosaccharides were derived from a novel unbranched, unsubstituted arabinoglucan (AGlc) polysaccharide. We identified sequences similar to the P. patens AGlc synthase from algae, bryophytes, lycophytes, and monilophytes, raising the possibility that other early divergent plants synthesize AGlc. Similarity of P. patens AGlc synthase to MLG synthases from ascomycetes, but not those from Poaceae, suggests that AGlc and MLG have a common evolutionary history that includes loss in seed plants, followed by a more recent independent origin of MLG within the monocots.