The biosynthesis of the unique cyanobacterial (oxyphotobacterial) indole-phenolic UVA sunscreen, scytonemin, is coded for in a conserved operon that contains both core metabolic genes and accessory, aromatic amino acid biosynthesis genes dedicated to supplying scytonemin's precursors. Comparative genomics shows conservation of this operon in many, but not all, cyanobacterial lineages. Phylogenetic analyses of the operon's aromatic amino acid genes indicate that five of them were recruited into the operon after duplication events of their respective house-keeping cyanobacterial cognates. We combined the fossil record of cyanobacteria and relaxed molecular clock models to obtain multiple estimates of these duplication events, setting a minimum age for the evolutionary advent of scytonemin at 2.1 +/- 0.3 billion years. The same analyses were used to estimate the advent of cyanobacteria as a group (and thus the appearance of oxygenic photosynthesis), at 3.6 +/- 0.2 billion years before present. Post hoc interpretation of 16S rRNA-based Bayesian analyses was consistent with these estimates. Because of physiological constraints on the use of UVA sunscreens in general, and the biochemical constraints of scytonemin in particular, scytonemin's age must postdate the time when Earth's atmosphere turned oxic, known as the Great Oxidation Event (GOE). Indeed, our biological estimate is in agreement with independent geochemical estimates for the GOE. The difference between the estimated ages of oxygenic photosynthesis and the GOE indicates the long span (on the order of a billion years) of the era of "oxygen oases," when oxygen was available locally but not globally. IMPORTANCE The advent of cyanobacteria, with their invention of oxygenic photosynthesis, and the Great Oxidation Event are arguably among the most important events in the evolutionary history of life on Earth. Oxygen is a significant toxicant to all life, but its accumulation in the atmosphere also enabled the successful development and proliferation of many aerobic organisms, especially metazoans. The currently favored dating of the Great Oxidation Event is based on the geochemical rock record. Similarly, the advent of cyanobacteria is also often drawn from the same estimates because in older rocks paleontological evidence is scarce or has been discredited. Efforts to obtain molecular evolutionary alternatives have offered widely divergent estimates. Our analyses provide a novel means to circumvent these limitations and allow us to estimate the large time gap between the two events.