Evidence for locomotion in the Precambrian fossil record is scant. Reliable Ediacaran trace fossils are all younger than 560 Ma, and consist of relatively simple horizontal burrows and trails from shallow-water deposits. Here we describe an assemblage of macroscopic locomotory traces from deep-water environments at Mistaken Point, southeastern Newfoundland, Canada, dated to ca. 565 Ma. These trails extend the record of complex trace fossils back into the earliest Avalonian biota. Our new evidence for large motile organisms on the seafloor at this time suggests that at least some of these early Ediacaran organisms, whose biological affinities are widely debated, could have been muscular and of metazoan grade.