Numerous evolutionary innovations were required to enable freshwater green algae to colonize terrestrial habitats and thereby initiate the evolution of land plants (embryophytes). These adaptations probably included changes in cell-wall composition and architecture that were to become essential for embryophyte development and radiation. However, it is not known to what extent the polymers that are characteristic of embryophyte cell walls, including pectins, hemicelluloses, glycoproteins and lignin, evolved in response to the demands of the terrestrial environment or whether they pre-existed in their algal ancestors. Here we show that members of the advanced charophycean green algae (CGA), including the Charales, Coleochaetales and Zygnematales, but not basal CGA (Klebsormidiales and Chlorokybales), have cell walls that are comparable in several respects to the primary walls of embryophytes. Moreover, we provide both chemical and immunocytochemical evidence that selected Coleochaete species have cell walls that contain small amounts of lignin or lignin-like polymers derived from radical coupling of hydroxycinnamyl alcohols. Thus, the ability to synthesize many of the components that characterize extant embryophyte walls evolved during divergence within CGA. Our study provides new insight into the evolutionary window during which the structurally complex walls of embryophytes originated, and the significance of the advanced CGA during these events.