Multicellular eukaryotes are characterized by an expanded extracellular matrix (ECM) with a diversified composition. The ECM is involved in determining tissue texture, screening cells from the outside medium, development, and innate immunity, all of which are essential features in the biology of multicellular eukaryotes. This review addresses the origin and evolution of the ECM, with a focus on multicellular marine algae. We show that in these lineages the expansion of extracellular matrix played a major role in the acquisition of complex multicellularity through its capacity to connect, position, shield, and defend the cells. Multiple innovations were necessary during these evolutionary processes, leading to striking convergences in the structures and functions of the ECMs of algae, animals, and plants.