Nonsense-mediated RNA decay (NMD) is an mRNA surveillance mechanism which rapidly degrades select cytoplasmic mRNAs. We and others have shown that NMD is a dynamically regulated process inhibited by amino acid deprivation, hypoxia, and other cellular stresses commonly generated by the tumor microenvironment. This inhibition of NMD can result in the accumulation of misfolded, mutated, and aggregated proteins, but how cells adapt to these aberrant proteins is unknown. Here we demonstrate that the inhibition of NMD activates autophagy, an established protein surveillance mechanism, both in vitro and in vivo. Conversely, the hyperactivation of NMD blunts the induction of autophagy in response to a variety of cellular stresses. The regulation of autophagy by NMD is due, in part, to stabilization of the documented NMD target ATF4. NMD inhibition increases intracellular amino acids, a hallmark of autophagy, and the concomitant inhibition of autophagy and NMD, either molecularly or pharmacologically, leads to synergistic cell death. Together these studies indicate that autophagy is an adaptive response to NMD inhibition and uncover a novel relationship between an mRNA surveillance system and a protein surveillance system, with important implications for the treatment of cancer.