Recombinant methioninase (rMETase) derived from Pseudomonas putida targets the elevated methionine (MET) requirement of cancer cells (methionine dependence) and has shown efficacy against a variety of cancer types in mouse models. To enhance the efficacy of rMETase, we constructed the pLGFP-METSN retrovirus encoding the P. putida methioninase (METase) gene fused with the green fluorescent protein (GFP) gene. pLGFP-METSN or control vector pLGFPSN was introduced into the human lung cancer cell line H460. The retrovirus-mediated METase gene transfer decreased the intracellular MET level of the cancer cells and consequently enhanced the efficacy of treatment with the rMETase protein. The rMETase gene was introduced into an adenovirus. rAd-METase transduction of human OVACAR-8 ovarian cancer cells and human fibrosarcoma HT1080 cells in vitro and in vivo resulted in high levels of METase expression up to 10% or more of the total protein of the cells, depending on the multiplicity of infection. The combination of rAd-METase and rMETase was synergistic to kill these cells. Normal fibroblasts, on the other hand, appeared relatively resistant to the METase gene in the presence of rMETase. Adenoviral METase-transduced cancer cells were used in combination with selenomethionine, releasing highly toxic methylselenol, which killed both the cancer cells containing the METase gene and bystanders. Methylselenol damaged the mitochondria via oxidative stress and caused cytochrome c release into the cytosol, thereby activating the caspase cascade and cancer-cell apoptosis. Adenoviral METase-gene/SeMET treatment also inhibited tumor growth in rodents and significantly prolonged their survival. AdMETase/SeMET therapy was effective against Bcl-2-overproducing A549 lung cancer cells, which were resistant to staurosporine-induced apoptosis, with a strong bystander effect. The combination of Ad-METase/SeMET and doxorubicin (DOX) delayed the growth of the H460 human lung cancer, growing subcutaneously in nude mice. These results demonstrate the potential of methionine restriction (MR) for cancer treatment.