The earliest forms of life on Earth were prokaryotes, & they dominated the biosphere for around 2.5 billion years. And slowly they changed it - aerobic photosynthesis by cyanobacteria ('blue-green algae') led first to the oxygenation of the oceans & then to the development of an oxygen-rich atmosphere (incidentally making life impossible for many anaerobic bacteria). Then, beginning about 1 billion years ago, we start to see evidence of eukaryote organisms in the fossil record. Perhaps the best-known are the (relatively) recent animals of the Cambrian (c. 540 million years ago), but there are also the strange organisms of the Ediacaran fauna. And, from fine-grained Chinese sandstones dating to between 635 & 551 mya, come what may be the earliest microscopic animal fossils (eggs, embryos & cysts), many of them preserved in beautiful detail. (There was some disagreement about the nature of these fossils, with a suggestion that they might actually represent prokaryote cells, but other discoveries seem to have ruled this out. NB that last link might not work for all.)
So what happened, around 1 billion years ago, that saw eukaryote animals begin to flourish? The increasing availability of oxygen must have been part of it. However, other changes in ocean chemistry may have been key to the evolution of multicellular animals (Narbonne, 2010) & researchers have been able to identify these changes by examining changes in the nature of sediments that formed in those ancient oceans. Examination of strata from the Doushantuo Formation (635-551 mya) in China indicate that the waters in which these sediments were laid down were anoxic (lacking in oxygen) & also strongly stratified, with chemically-different layers of water sitting one on top of the other. The researchers also inferred that there'd have been a thin layer of oxygenated water sitting on top of those anoxic layers.
Up to about 740 mya such oxygenated layers were apparently rare, which would have reduced the odds of any animals evolving - after all, animals need oxygen. It's assumed that the Doushanto organisms lived in a thin surface layer of oxygenated water & were deposited in anoxic sediments when they died (the lack of oxygen in those sediments helps to explain their excellent preservation). It seems that the world's oceans didn't start to become oxygenated at depth until about 580 mya, a change that would have set the stage for the subsequent evolution of the much larger, multicellular animals of the late Ediacaran & following Cambrian periods.
G.Narbonne (2010) Ocean chemistry and early animals. Science 328: 53-54