Cancer cells have high demands for non-essential amino acids (NEAAs), which are precursors for anabolic and antioxidant pathways that support cell survival and proliferation. It is well-established that cancer cells consume the NEAA cysteine, and that cysteine deprivation can induce cell death; however, the specific factors governing acute sensitivity to cysteine starvation are poorly characterized. Here, we show that that neither expression of enzymes for cysteine synthesis nor availability of the primary precursor methionine correlated with acute sensitivity to cysteine starvation. We observed a strong correlation between efflux of the methionine-derived metabolite methylthioadenosine (MTA) and sensitivity to cysteine starvation. MTA efflux results from genetic deletion of methylthioadenosine phosphorylase (MTAP), which is frequently deleted in cancers. We show that MTAP loss upregulates polyamine metabolism which, concurrently with cysteine withdrawal, promotes elevated reactive oxygen species and prevents cell survival. Our results reveal an unexplored metabolic weakness at the intersection of polyamine and cysteine metabolism.