The targeted therapy of metastatic melanoma is an important yet challenging goal that has received only limited attention to date. Herein, green tea polyphenols, (–)-epigallocatechin-3-gallate (EGCG), and lanthanide metal ions (Sm3+) are used as building blocks to engineer self-assembled SmIII-EGCG nanocomplexes with synergistically enhanced tumor inhibitory properties. These nanocomplexes have negligible systemic toxic effects on healthy cells but cause a significant reduction in the viability of melanoma cells by efficiently regulating their metabolic pathways. Moreover, the wound-induced migration of melanoma cells can be efficiently inhibited by SmIII-EGCG, which is a key criterion for metastatic melanoma therapy. In a mouse melanoma tumor model, SmIII-EGCG is directly compared with a clinical anticancer drug, 5-fluorouracil and shows remarkable tumor inhibition. Moreover, the targeted therapy of SmIII-EGCG is shown to prevent metastatic lung melanoma from spreading to main organs with no adverse side effects on the body weight or organs. These in vivo results demonstrate significant advantages of SmIII-EGCG over its clinical counterpart. The results suggest that these green tea-based, self-assembled nanocomplexes possess all of the key traits of a clinically promising candidate to address the challenges associated with the treatment of advanced stage metastatic melanoma.