Fossils of the Ediacaran macrobiota (∼571-539 mya) record phylogenetically diverse marine palaeocommunities, including early animals, which pre-date the "Cambrian Explosion" [1-4]. Benthic forms with a frondose gross morphology, assigned to the morphogroups Rangeomorpha [5] and Frondomorpha (see also Arboreomorpha) [6-8], are among the most temporally wide-ranging and environmentally tolerant members of the Ediacaran macrobiota [6] and dominated deep-marine ecosystems ∼571-560 mya [9-11]. Investigations into the morphology [12-14], palaeoecology [10, 15, 16], reproductive strategies [17, 18], feeding methods [9, 19], and morphogenesis of frondose taxa together constrain their phylogenetic position to the metazoan (for Rangeomorpha) or eumetazoan (e.g., Arborea) total groups [14, 20], but tighter constraint is currently lacking. Here, we describe fossils of abundant filamentous organic structures preserved among frond-dominated fossil assemblages in Newfoundland (Canada). The filaments constitute a prominent component of the ecosystems, and exhibit clear physical associations with at least seven frondose taxa. Individual specimens of one uniterminal rangeomorph taxon appear to be directly connected by filaments across distances of centimeters to meters. Such physical linkages are interpreted to reflect evidence for stolonic connections: a conclusion with potential implications for the phylogenetic placement and palaeoecology of frondose organisms. Consideration of extant stoloniferous organisms suggests that Ediacaran frondose taxa were likely clonal and resurrects the possibility that they may have been colonial (e.g., [21, 22]). VIDEO ABSTRACT.