The ancestors of cyanobacteria generated Earth’s first biogenic molecular oxygen but how they dealt with its toxicity remains unconstrained. Here we investigated when superoxide dismutase enzymes (SODs) capable of removing superoxide free radicals evolved. We found phylogenetic evidence that ancestral cyanobacteria used SODs with copper and zinc cofactors (CuZnSOD) during the Archaean. By the Paleoproterozoic, they became genetically capable of using iron, nickel, and manganese as cofactors (FeSOD, NiSOD, and MnSOD respectively). The evolution of NiSOD is particularly intriguing because it has been previously hypothesized that declining seawater Ni concentrations at the end of the Archaean caused a fundamental shift in the marine biosphere away from methanogenesis towards oxygenic photosynthesis. Our novel analyses of enzymes dealing with O2 toxicity now demonstrate that the beneficiaries of this chemical change - marine planktonic cyanobacteria - were able to utilize the remaining Ni from seawater 0.9-0.8 Ga to supplement their existing metabolic capabilities.