In plant and animal cells, amino-terminal cysteine oxidation controls selective proteolysis via an oxygen-dependent branch of the N-end rule pathway. It remains unknown how the N-terminal cysteine is specifically oxidized. Here we identify plant cysteine oxidase (PCO) enzymes that oxidize the penultimate cysteine of ERF-VII transcription factors by using oxygen as a co-substrate, thereby controlling the lifetime of these proteins. Consequently, ERF-VII proteins are stabilized under hypoxia and activate the molecular response to low oxygen while the expression of anaerobic genes is repressed in air. Members of the PCO family are themselves targets of ERF-VII transcription factors, generating a feedback loop that adapts the stress response according to the extent of the hypoxic condition. Our results reveal that PCOs act as sensor proteins for oxygen in plants and provide an example of how proactive regulation of the N-end rule pathway balances stress response to optimal growth and development in plants.