Methionine dependence represents a well-known metabolic vulnerability in cancer. Despite promising preclinical results, methionine restriction is impaired by the presence of methionine-independent cancer cells. After confirming both inter- and intra-tumoral heterogeneity in methionine dependence, we demonstrate that "methionine-independent" cells are rather "methionine self-sufficient," relying on the vitamin B12 (B12)-dependent methionine synthase (MTR) to sustain growth without exogenous methionine, which renders them highly vulnerable to B12 deprivation. Dual methionine and B12 deprivation produced synergistic cytotoxicity, inhibiting proliferation and inducing apoptosis across multiple cancer types and primary tumor cells, while sparing fibroblasts. This synergy persisted under moderate nutrient restriction, supporting translational potential. Moreover, dual therapy prevented the adaptive metabolic shift seen with methionine deprivation alone, avoiding rebound proliferation and resistance. In vivo, a methionine-restricted diet plus a synthesized B12 antagonist significantly suppressed growth of methionine-independent pancreatic xenografts without hematologic toxicity. These findings uncover a selective, synergistic anticancer strategy targeting methionine self-sufficiency.