One of the most profound events in biospheric evolution was the emergence of animals, which is thought to have occurred some 600–650 Ma. Here we report on the discovery of phosphatised body fossils that we interpret as ancient sponge-like fossils and term them Otavia antiqua gen. et sp. nov. The fossils are found in Namibia in rocks that range in age between about 760 Ma and 550 Ma. This age places the advent of animals some 100 to 150 million years earlier than proposed, and prior to the extreme climatic changes and postulated stepwise increases in oxygen levels of Ediacaran time. These findings support the predictions based on genetic sequencing and inferences drawn from biomarkers that the first animals were sponges. Further, the deposition and burial of Otavia as sedimentary particles may have driven the large positive C-isotopic excursions and increases in oxygen levels that have been inferred for Neoproterozoic time.