Nitric oxide exerts a plethora of biological effects via protein S-nitrosylation, a redox-based reaction that converts a protein Cys thiol to a S-nitrosothiol. However, although the regulation of protein S-nitrosylation has been the subject of extensive study, much less is known about the systems governing protein denitrosylation. Most recently, thioredoxin/thioredoxin reductases were shown to mediate both basal and stimulus-coupled protein denitrosylation. We now demonstrate that protein denitrosylation by thioredoxin is regulated dynamically by thioredoxin-interacting protein (Txnip), a thioredoxin inhibitor. Endogenously synthesized nitric oxide represses Txnip, thereby facilitating thioredoxin-mediated denitrosylation. Autoregulation of denitrosylation thus allows cells to survive nitrosative stress. Our findings reveal that denitrosylation of proteins is dynamically regulated, establish a physiological role for thioredoxin in protection from nitrosative stress, and suggest new approaches to manipulate cellular S-nitrosylation.