NK cells are highly efficient at preventing cancer metastasis but are infrequently found in the core of primary tumors. Here, have we demonstrated that freshly isolated mouse and human NK cells express low levels of the endo-β-D-glucuronidase heparanase that increase upon NK cell activation. Heparanase deficiency did not affect development, differentiation, or tissue localization of NK cells under steady-state conditions. However, mice lacking heparanase specifically in NK cells (Hpsefl/fl NKp46-iCre mice) were highly tumor prone when challenged with the carcinogen methylcholanthrene (MCA). Hpsefl/fl NKp46-iCre mice were also more susceptible to tumor growth than were their littermate controls when challenged with the established mouse lymphoma cell line RMA-S-RAE-1β, which overexpresses the NK cell group 2D (NKG2D) ligand RAE-1β, or when inoculated with metastatic melanoma, prostate carcinoma, or mammary carcinoma cell lines. NK cell invasion of primary tumors and recruitment to the site of metastasis were strictly dependent on the presence of heparanase. Cytokine and immune checkpoint blockade immunotherapy for metastases was compromised when NK cells lacked heparanase. Our data suggest that heparanase plays a critical role in NK cell invasion into tumors and thereby tumor progression and metastases. This should be considered when systemically treating cancer patients with heparanase inhibitors, since the potential adverse effect on NK cell infiltration might limit the antitumor activity of the inhibitors.