The enzymatic conjugation of arginine to the N-termini of proteins is a part of the ubiquitin-dependent N-end rule pathway of protein degradation. In mammals, three N-terminal residues-aspartate, glutamate, and cysteine-are substrates for arginylation. The mouse ATE1 gene encodes a family of Arg-tRNA-protein transferases (R-transferases) that mediate N-terminal arginylation. We constructed ATE1-lacking mouse strains and found that ATE1-/- embryos die with defects in heart development and in angiogenic remodeling of the early vascular plexus. Through biochemical analyses, we show that N-terminal cysteine, in contrast to N-terminal aspartate and glutamate, is oxidized before its arginylation by R-transferase, suggesting that the arginylation branch of the N-end rule pathway functions as an oxygen sensor.