Ten phosphatized specimens of a small (<180 micrometers) animal displaying clear bilaterian features have been recovered from the Doushantuo Formation, China, dating from 40 to 55 million years before the Cambrian. Seen in sections, this animal (Vernanimalcula guizhouena gen. et sp. nov.) had paired coeloms extending the length of the gut; paired external pits that could be sense organs; bilateral, anterior-posterior organization; a ventrally directed anterior mouth with thick walled pharynx; and a triploblastic structure. The structural complexity is that of an adult rather than a larval form. These fossils provide the first evidence confirming the phylogenetic inference that Bilateria arose well before the Cambrian.