Eukaryotic multicellularity originated in the Mesoproterozoic Era and evolved multiple times since, yet early multicellular fossils are scarce until the terminal Neoproterozoic and often restricted to cases of exceptional preservation. Here we describe unusual organically-preserved fossils from mudrocks, that provide support for the presence of organisms with differentiated cells (potentially an epithelial layer) in the late Neoproterozoic. Cyathinema digermulense gen. et sp. nov. from the Nyborg Formation, Vestertana Group, Digermulen Peninsula in Arctic Norway, is a new carbonaceous organ-taxon which consists of stacked tubes with cup-shaped ends. It represents parts of a larger organism (multicellular eukaryote or a colony), likely with greater preservation potential than its other elements. Arrangement of open-ended tubes invites comparison with cells of an epithelial layer present in a variety of eukaryotic clades. This tissue may have benefitted the organism in: avoiding overgrowth, limiting fouling, reproduction, or water filtration. C. digermulense shares characteristics with extant and fossil groups including red algae and their fossils, demosponge larvae and putative sponge fossils, colonial protists, and nematophytes. Regardless of its precise affinity, C. digermulense was a complex and likely benthic marine eukaryote exhibiting cellular differentiation, and a rare occurrence of early multicellularity outside of Konservat-Lagerstätten.