Photosystem II, the water oxidizing enzyme, altered the course of evolution by filling the atmosphere with oxygen. Here, we reconstruct the origin and evolution of water oxidation at an unprecedented level of detail by studying the phylogeny of all D1 subunits, the main protein coordinating the water oxidizing cluster (Mn4CaO5) of Photosystem II. We show that D1 exists in several forms making well-defined clades, some of which could have evolved before the origin of water oxidation and presenting many atypical characteristics. The most ancient form is found in the genome of Gloeobacter kilaueensis JS-1 and this has a C-terminus with a higher sequence identity to D2 than to any other D1. Two other groups of early evolving D1 correspond to those expressed under prolonged far-red illumination and in darkness. These atypical D1 forms are characterized by a dramatically different Mn4CaO5 binding site and a Photosystem II containing such a site may assemble an unconventional metal cluster. The first D1 forms with a full set of ligands to the Mn4CaO5 cluster are grouped with D1 proteins expressed only under low oxygen concentrations and the latest evolving form is the dominant type of D1 found in all cyanobacteria and plastids. In addition, we show that the plastid ancestor had a D1 more similar to those in early branching Synechococcus. We suggest each one of these forms of D1 originated from transitional forms at different stages towards the innovation and optimization of water oxidation before the last common ancestor of all known cyanobacteria.