Cancer metastasis is a leading cause of cancer morbidity and mortality. More needs to be learned about mechanisms that control this process. In particular, the role of chemokine receptors in metastasis remains controversial. Here, using a highly metastatic breast cancer (4T1) model, we show that lung metastasis is a feature of only a proportion of the tumor cells that express CCR4. Moreover, the primary tumor growing in mammary pads activates remotely the expression of TARC/CCL17 and MDC/CCL22 in the lungs. These chemokines acting through CCR4 attract both tumor and immune cells. However, CCR4-mediated chemotaxis was not sufficient to produce metastasis, as tumor cells in the lung were efficiently eliminated by natural killer (NK) cells. Lung metastasis required CCR4(+) regulatory T cells (Treg), which directly killed NK cells using beta-galactoside-binding protein. Thus, strategies that abrogate any part of this process should improve the outcome through activation of effector cells and prevention of tumor cell migration. We confirm this prediction by killing CCR4(+) cells through delivery of TARC-fused toxins or depleting Tregs and preventing lung metastasis.