Current models predict that the early atmosphere consisted mostly of CO2, N2, and H2O, along with traces of H2 and CO. Such models are based on the assumption that the redox state of the upper mantle has not changed, so that volcanic gas composition has remained approximately constant with time. We argue here that this assumption is probably incorrect: the upper mantle was originally more reduced than today, although not as reduced as the metal arrest level, and has become progressively more oxidized as a consequence of the release of reduced volcanic gases and the subduction of hydrated, oxidized seafloor. Data on the redox state of sulfide and chromite inclusions in diamonds imply that the process of mantle oxidation was slow, so that reduced conditions could have prevailed for as much as half of the earth's history. To be sure, other oxybarometers of ancient rocks give different results, so the question of when the mantle redox state has changed remains unresolved. Mantle redox evolution is intimately linked to the oxidation state of the primitive atmosphere: A reduced Archean atmosphere would have had a high hydrogen escape rate and should correspond to a changing mantle redox state; an oxidized Archean atmosphere should be associated with a constant mantle redox state. The converses of these statements are also true. Finally, our theory of mantle redox evolution may explain why the Archean atmosphere remained oxygen-deficient until approximately 2.0 billion years ago (Ga) despite a probable early origin for photosynthesis.