In higher plants, molecular responses to exogenous hypoxia are driven by group VII ethylene response factors (ERF-VIIs). These transcriptional regulators accumulate in the nucleus under hypoxia to activate anaerobic genes but are destabilized in normoxic conditions through the action of oxygen-sensing plant cysteine oxidases (PCOs). The PCOs catalyze the reaction of oxygen with the conserved N-terminal cysteine of ERF-VIIs to form cysteine sulfinic acid, triggering degradation via the Cys/Arg branch of the N-degron pathway. The PCOs are therefore a vital component of the plant oxygen signaling system, connecting environmental stimulus with cellular and physiological response. Rational manipulation of PCO activity could regulate ERF-VII levels and improve flood tolerance, but requires detailed structural information. We report crystal structures of the constitutively expressed PCO4 and PCO5 from Arabidopsis thaliana to 1.24 and 1.91 Å resolution, respectively. The structures reveal that the PCOs comprise a cupin-like scaffold, which supports a central metal cofactor coordinated by three histidines. While this overall structure is consistent with other thiol dioxygenases, closer inspection of the active site indicates that other catalytic features are not conserved, suggesting that the PCOs may use divergent mechanisms to oxidize their substrates. Conservative substitution of two active site residues had dramatic effects on PCO4 function both in vitro and in vivo, through yeast and plant complementation assays. Collectively, our data identify key structural elements that are required for PCO activity and provide a platform for engineering crops with improved hypoxia tolerance.