Lignified cell walls are widely considered to be key innovations in the evolution of terrestrial plants from aquatic ancestors some 475 million years ago. Lignins, complex aromatic heteropolymers, stiffen and fortify secondary cell walls within xylem tissues, creating a dense matrix that binds cellulose microfibrils and crosslinks other wall components, thereby preventing the collapse of conductive vessels, lending biomechanical support to stems, and allowing plants to adopt an erect-growth habit in air. Although "lignin-like" compounds have been identified in primitive green algae, the presence of true lignins in nonvascular organisms, such as aquatic algae, has not been confirmed. Here, we report the discovery of secondary walls and lignin within cells of the intertidal red alga Calliarthron cheilosporioides. Until now, such developmentally specialized cell walls have been described only in vascular plants. The finding of secondary walls and lignin in red algae raises many questions about the convergent or deeply conserved evolutionary history of these traits, given that red algae and vascular plants probably diverged more than 1 billion years ago.