Shells, bones, tracks, and trails record a history of animal evolution more than 600 million years long. Earth, however, is some four and a half billion years old. What kinds of life characterized our planet's youth and middle age? Genealogical relationships among living organisms, inferred from molecular sequence comparisons, suggest that the deep history of life is microbial, and over the past three decades, paleontologists have discovered a rich record of microbial life in rocks that long predate the earliest animals. Geochemical research has established a complementary record of environmental change, with major transitions that parallel those found among fossils. The general pattern that emerges is one of long-term co-evolution between life and environments throughout our planetary history.