The first appearance of animals in the geological record is a matter of continuing debate: how deep were the roots of the Cambrian explosion? Molecular clock estimates indicate that the deepest divergences of the Metazoa had occurred by the Ediacaran Period (635–541 Ma), yet evidence of animal activity from well below the Ediacaran-Cambrian boundary has been rare and often questionable. Meanwhile, the Ediacaran macrobiota has remained enigmatic, as emphasized by recent controversial claims that South Australia Ediacaran forms were not marine animals at all, but land-based lichens and microbial colonies. Here we report evidence for animal-like behavior in a submerged setting in a key Ediacaran form, Aspidella terranovica Billings 1872, a discoidal fossil from the ca. 560 Ma Fermeuse Formation of Newfoundland (Canada). We describe sedimentary fabrics indicating progressive vertical movement of an organism through sediment in response to an aggrading sediment-water interface. Such equilibrium traces are familiar from the Phanerozoic and are observed in partially buried marine animals such as tube anemones today. Furthermore, horizontal trails closely comparable to trails previously described from ∼565 m.y. old Mistaken Point (Newfoundland) are now linked to Aspidella. Our findings constitute evidence of both vertical and horizontal movement in a key Ediacaran taxon, consistent with an animal of cnidarian grade. Moreover, because Aspidella is also reported from the Rawnsley Quartzite of South Australia, our evidence conflicts with the proposed radical interpretation of that Ediacaran fossil assemblage. We demonstrate that at least some Ediacaran forms were probably early animals, and that they lived underwater.