Constraining oxygen levels in the early Precambrian surface ocean has been a longstanding goal, but efforts have been challenged by the availability of suitable proxies. Here we present a novel approach, iodine geochemistry, which broadens our perspective by providing constraints on shallow, carbonate-dominated marine settings. Iodate (IO3–) persists exclusively in oxic waters and is the sole iodine species incorporated into carbonate minerals, allowing iodine-to-calcium ratios (I/Ca) in shallow carbonates to be used as a paleoredox indicator. Our data from a series of Mesoarchean through Paleoproterozoic carbonates deposited under shallow-marine conditions reveal a progressive surface ocean oxygenation in the early Paleoproterozoic. These data seem to indicate that a largely anoxic surface ocean extended throughout the Archean until the Great Oxidation Event (GOE) at ca. 2.4 Ga, implying that previous inferences of pre-GOE oxygen production may reflect oxygen oases, transient oxidation events, or oxygen levels below those required for IO3– accumulation. The data suggest formation and persistence of IO3– and, consequently, surface ocean oxygen concentrations of at least 1 μM during the GOE. Following the initial rise of oxygen, carbonate-associated iodine in globally extensive carbonate units deposited during the Lomagundi positive carbon isotope excursion at ca. 2.22–2.1 Ga suggests a widespread aerobic iodine cycle beyond that operating prior to the event, synchronous with high relative rates of organic carbon burial and apparent expansion of oxidative conditions.