The multicellular algae are the core topic for understanding the early life evolution on Earth. The timing of origin and cellular differentiation of multicellular algae, however, remains poorly constrained. The Paleo- to early Mesoproterozoic is a critical period, during which multicellular algae began to occur and started to evolve in marine environments. This paper reports well-preserved multicellular fossils from shales of the Chuanlinggou Formation in North China, with emphasis on their holdfast structure and putative cellular structures. These macroalgae fossils are reasonably diversified in this formation, and include Chuaria circularis, Tawuia sinensis, Tawuia robusta, Glossophyton ovalis, Glossophyton sp., Tuanshanzia sp., Changchengia sp., which are mainly preserved as carbonaceous compressions, with some in sideritized forms. FESEM observation reveals multicellular structures in Chuaria, confirming its biological attribute of multicellular eukaryote and providing direct evidence that multicellular algae had already originated by the terminal Paleoproterozoic, earlier than previous speculation. The Tuanshanzia sp. and Changchengia sp. developed with bare rhizome holdfast, suggesting their benthic sessile lifestyle in the late Paleoproterozoic oceanic habitat.