The scientists behind it say the development of bilateral symmetry was a critical step in the evolution of animal life.
It gave organisms the ability to move purposefully and a common, yet successful way to organise their bodies.
A multitude of animals, from worms to insects to dinosaurs to humans, are organised around this same basic bilaterian body plan.
Scott Evans, of the University of California at Riverside, and colleagues have called the organism Ikaria wariootia.
It lived 555 million years ago during what geologists term as the Ediacaran Period - the time in Earth history when life started to become multi-celled and much more complex.
The discovery started with tiny burrows being identified in rocks in Nilpena, South Australia, some 15 years ago.
Many who looked at these traces recognised they were likely made by bilaterians, but creatures' presence in the ancient deposits was not obvious.
It was only recently that Scott Evans and Mary Droser, a professor of geology at UC Riverside, noticed minuscule, oval impressions near some of the burrows.
Three-dimensional laser scanning revealed the regular, consistent shape of a cylindrical body with a distinct head and tail and faintly grooved musculature.
Ikaria wariootia ranged in size between 2mm and 7mm long, and about 1-2.5mm wide. The largest of the ovals was just the right size and shape to have made the long-recognised burrows.
"We thought these animals should have existed during this interval, but always understood they would be difficult to recognise," Scott Evans said. "Once we had the 3D scans, we knew that we had made an important discovery."
Ikaria wariootia probably spent its life burrowing through layers of sand on the ocean floor, looking for any organic matter on which it could feed.