The conjugation of arginine to proteins is a part of the N-end rule pathway of protein degradation. Three amino (N)-terminal residues—aspartate, glutamate and cysteine—are arginylated by ATE1-encoded arginyl-transferases. Here we report that oxidation of N-terminal cysteine is essential for its arginylation. The in vivo oxidation of N-terminal cysteine, before its arginylation, is shown to require nitric oxide. We reconstituted this process in vitro as well. The levels of regulatory proteins bearing N-terminal cysteine, such as RGS4, RGS5 and RGS16, are greatly increased in mouse ATE1^-/- embryos, which lack arginylation. Stabilization of these proteins, the first physiological substrates of mammalian N-end rule pathway, may underlie cardiovascular defects in ATE1^-/- embryos. Our findings identify the N-end rule pathway as a new nitric oxide sensor that functions through its ability to destroy specific regulatory proteins bearing N-terminal cysteine, at rates controlled by nitric oxide and apparently by oxygen as well.