During epithelial-mesenchymal transition (EMT) epithelial cancer cells transdifferentiate into highly motile, invasive, mesenchymal-like cells, giving rise to disseminating tumor cells. Few of these disseminated cells successfully metastasize. Immune cells and inflammation in the tumor microenvironment were shown to drive EMT, but few studies investigated the consequences of EMT for tumor immunosurveillance. In addition to initiating metastasis, we demonstrate that EMT confers increased susceptibility to natural killer (NK) cells and contributes, in part, to the inefficiency of the metastatic process. Depletion of NK cells allowed spontaneous metastasis without affecting primary tumor growth. EMT-induced modulation of E-cadherin and cell adhesion molecule 1 (CADM1) mediated increased susceptibility to NK cytotoxicity. Higher CADM1 expression correlates with improved patient survival in 2 lung and 1 breast adenocarcinoma patient cohorts and decreased metastasis. Our observations reveal a novel NK-mediated, metastasis-specific immunosurveillance in lung cancer and present a window of opportunity for preventing metastasis by boosting NK cell activity.