Molecular phylogenetic data suggest that photosynthetic eukaryotes first evolved in freshwater environments in the early Proterozoic and diversified into marine environments by the Tonian Period, but early algal evolution is poorly reflected in the fossil record. Here, we report newly discovered, millimeter- to centimeter-scale macrofossils from outer-shelf marine facies of the ca. 950–900 Ma (Re-Os minimum age constraint = 898 ± 68 Ma) Dolores Creek Formation in the Wernecke Mountains, northwestern Canada. These fossils, variably preserved by iron oxides and clay minerals, represent two size classes. The larger forms feature unbranching thalli with uniform cells, differentiated cell walls, longitudinal striations, and probable holdfasts, whereas the smaller specimens display branching but no other diagnostic features. While the smaller population remains unresolved phylogenetically and may represent cyanobacteria, we interpret the larger fossils as multicellular eukaryotic macroalgae with a plausible green algal affinity based on their large size and presence of rib-like wall ornamentation. Considered as such, the latter are among the few green algae and some of the largest macroscopic eukaryotes yet recognized in the early Neoproterozoic. Together with other Tonian fossils, the Dolores Creek fossils indicate that eukaryotic algae, including green algae, colonized marine environments by the early Neoproterozoic Era.