Prostate cancer, the leading incidence of cancer in American males, is a disease in which treatment of nonlocalized tumors remains largely unsuccessful. These cancers lose expression of an arginine synthesis enzyme, argininosuccinate synthetase (ASS), and are susceptible to arginine deprivation by arginine deiminase (ADI). We show CWR22Rv1 prostate cancer cells are susceptible to ADI in a caspase-independent manner in vitro and in a xenograft model in vivo. We demonstrate that single amino acid deprivation by ADI is able to trigger autophagy. Inhibition of autophagy by chloroquine and siRNA enhances and accelerates ADI-induced cell death, suggesting that autophagy is a protective response to ADI, at least in the early phases. In addition, the co-administration of docetaxel, a caspase-dependent chemotherapy, with ADI inhibits tumor growth in vivo. Thus, targeting multiple cell death pathways, either through autophagy modulation or non-canonical apoptosis, may find expanded use as adjuvant chemotherapies, providing additional avenues for cancer treatment.