Amino acid deprivation therapy (AADT) is a promising strategy for developing novel anticancer treatments, based on variations in metabolism of healthy and malignant cells. L-asparaginase was the first amino acid-degrading enzyme that received FDA approval for the treatment of acute lymphoblastic leukemia (ALL). Arginase and arginine deiminase were effective in clinical trials for the treatment of metastatic melanomas and hepatocellular carcinomas. Essential dependence of certain cancer cells on methionine explains the anticancer efficacy of methionine-g-lyase. Along with significant progress in identification of metabolic vulnerabilities of cancer cells, new amino acid-cleaving enzymes appear as promising agents for cancer treatment: lysine oxidase, tyrosine phenol-lyase, cysteinase, and phenylalanine ammonia-lyase. However, sensitivity of specific cancer cell types to these enzymes differs. Hence, search for prognostic and predictive markers for AADT and introduction of the markers into clinical practice are of great importance for translational medicine. As specific metabolic pathways in cancer cells are determined by the enzyme expression, some of these enzymes may define the sensitivity to AADT. This review considers the known predictors for efficiency of AADT, emphasizing the importance of knowledge on cancer-specific amino acid significance for such predictions.