The first multicellular complex animals of any sort appear in the fossil record about 600 to 590 million years ago, specifically in the Twitya Formation in the Mackenzie Mountains of Canada. These are simple cup-shaped animals that appear in fossil form as simple disc and ring impressions. They are thought to correspond to simple cnidarians (relatives of jellyfish) or sponges. Because they are so simple, these fossils confer little information about the animals that made them. However, they are still considered "complex" because of their very large size (about an inch in diameter) compared to the simpler microscopic, unicellular fossils from before and alongside them.
The next oldest complex animals preserved as fossils appear in the Doushantuo Formation in south-central China. A wide variety of fossil embryos are preserved, as well as the earliest known bilateral animal, the 0.1 mm Vernanimacula (about 590 to 600 mya), the "small springtime animal," a tiny sphere-shaped animal with what appears to be a fossilized gut, as well as surface pits that may be sensory structures. Tiny fossil embryos of complex animals, such as cnidarians, are preserved to an unparalleled degree of detail in the Doushantuo Formation, giving paleontologists important insight into the earliest embryos known.
Another early fossil among complex animals is the enigmatic Cloudina, a segmented fossil consisting of calcite cones layered on each other. Measured in increments of millimeters, these fossils are among the first known shells in the fossil record. They display budding, which suggests they reproduced asexually, as well as predatory boring, which shows that there were predators even at the very dawn of known multicellular life. Like many of the earliest fossils, there is a lack of uncertainty as to what exactly Cloudina was -- current opinion is divided between the idea that the specimen is a stem group annelid and that any classification, even at the phylum level, is unwise. They may be archaeocyathids, ancient sponges that built reefs hundreds of millions of years before the evolution of coral.
The first truly "complex animals" (larger than 1 mm, not cnidarians or corals) fossils are about 575 million years old, and are found at the Mistaken Point assemblage in Newfoundland, Canada. The absolute oldest is Charnia wardi, a frond-shaped organism with left-and-right alternating ridges. Because these ridges are not completely symmetrical around the central axis, Charnia is not a true bilateral organism, and can only be described as semi-bilaterial. Initially described as an early relative of sea pens, scientists now simply have no idea how to classify Charnia.