• Brown algal cell walls share some components with plants (cellulose) and animals (sulfated fucans), but they also contain some unique polysaccharides (alginates). Analysis of the Ectocarpus genome provides a unique opportunity to decipher the molecular bases of these crucial metabolisms. • An extensive bioinformatic census of the enzymes potentially involved in the biogenesis and remodeling of cellulose, alginate and fucans was performed, and completed by phylogenetic analyses of key enzymes. • The routes for the biosynthesis of cellulose, alginates and sulfated fucans were reconstructed. Surprisingly, known families of cellulases, expansins and alginate lyases are absent in Ectocarpus, suggesting the existence of novel mechanisms and/or proteins for cell wall expansion in brown algae. • Altogether, our data depict a complex evolutionary history for the main components of brown algal cell walls. Cellulose synthesis was inherited from the ancestral red algal endosymbiont, whereas the terminal steps for alginate biosynthesis were acquired by horizontal gene transfer from an Actinobacterium. This horizontal gene transfer event also contributed genes for hemicellulose biosynthesis. By contrast, the biosynthetic route for sulfated fucans is an ancestral pathway, conserved with animals. These findings shine a new light on the origin and evolution of cell wall polysaccharides in other Eukaryotes.