The evolution of Earth's biota is intimately linked to the oxygenation of the oceans and atmosphere. We use the isotopic composition and concentration of molybdenum (Mo) in sedimentary rocks to explore this relationship. Our results indicate two episodes of global ocean oxygenation. The first coincides with the emergence of the Ediacaran fauna, including large, motile bilaterian animals, ca. 550-560 million year ago (Ma), reinforcing previous geochemical indications that Earth surface oxygenation facilitated this radiation. The second, perhaps larger, oxygenation took place around 400 Ma, well after the initial rise of animals and, therefore, suggesting that early metazoans evolved in a relatively low oxygen environment. This later oxygenation correlates with the diversification of vascular plants, which likely contributed to increased oxygenation through the enhanced burial of organic carbon in sediments. It also correlates with a pronounced radiation of large predatory fish, animals with high oxygen demand. We thereby couple the redox history of the atmosphere and oceans to major events in animal evolution.