Brown algae are photosynthetic multicellular marine organisms evolutionarily distant from land plants, with a distinctive cell wall. They feature carbohydrates shared with plants (cellulose), animals (fucose-containing sulfated polysaccharides, FCSPs) or bacteria (alginates). How these components are organized into a three-dimensional extracellular matrix (ECM) still remains unclear. Recent molecular analysis of the corresponding biosynthetic routes points toward a complex evolutionary history that shaped the ECM structure in brown algae. Exhaustive sequential extractions and composition analyses of cell wall material from various brown algae of the order Fucales were performed. Dedicated enzymatic degradations were used to release and identify cell wall partners. This approach was complemented by systematic chromatographic analysis to study polymer interlinks further. An additional structural assessment of the sulfated fucan extracted from Himanthalia elongata was made. The data indicate that FCSPs are tightly associated with proteins and cellulose within the walls. Alginates are associated with most phenolic compounds. The sulfated fucans from H. elongata were shown to have a regular α-(1→3) backbone structure, while an alternating α-(1→3), (1→4) structure has been described in some brown algae from the order Fucales. The data provide a global snapshot of the cell wall architecture in brown algae, and contribute to the understanding of the structure-function relationships of the main cell wall components. Enzymatic cross-linking of alginates by phenols may regulate the strengthening of the wall, and sulfated polysaccharides may play a key role in the adaptation to osmotic stress. The emergence and evolution of ECM components is further discussed in relation to the evolution of multicellularity in brown algae.