Cyanobacterial aldehyde decarbonylase (AD) catalyzes conversion of fatty aldehydes (R-CHO) to alka(e)nes (R-H) and formate. Curiously, although this reaction appears to be redox-neutral and formally hydrolytic, AD has a ferritin-like protein architecture and a carboxylate-bridged dimetal cofactor that are both structurally similar to those found in di-iron oxidases and oxygenases. In addition, the in vitro activity of the AD from Nostoc punctiforme (Np) was shown to require a reducing system similar to the systems employed by these O-2-utilizing di-iron enzymes. Here, we resolve this conundrum by showing that aldehyde cleavage by the Np AD also requires dioxygen and results in incorporation of O-18 from 1802 into the formate product. AD thus oxygenates, without oxidizing, its substrate. We posit that (i) O-2 adds to the reduced cofactor to generate a metal-bound peroxide nucleophile that attacks the substrate carbonyl and initiates a radical scission of the C1-C2 bond, and (ii) the reducing system delivers two electrons during aldehyde cleavage, ensuring a redox-neutral outcome, and two additional electrons to return an oxidized form of the cofactor back to the reduced, O-2-reactive form.