Natural Killer (NK) cells are components of the innate immune system that play an important role in tumour clearance. Heparanase is a b-D-endoglucuronidase which cleaves the heparan sulphate (HS) side chains of heparan sulphate proteoglycans (HSPGs), a major component of the extracellular matrix and basement membrane. The expression and function of heparanase has been documented in selected leukocyte populations to aid migration, but as yet, has not been described in NK cells. This study shows for the first time that heparanase expression and activity is upregulated in activated human NK cells compared to naïve NK cells, and activated NK cells use heparanase to degrade the ECM in vitro. Furthermore, murine splenic NK cells are also shown to express heparanase and exhibit heparanase activity. Following Poly(I:C) challenge, mice deficient in heparanase were found to have impaired maturation status, cytokine secretion, and cytotoxicity against YAC-1 and EO771.LMB cells, as well as defects in migration. These findings establish that heparanase is expressed and utilised by murine and human NK cells, and that it is important for normal migration and function of NK cells in a tumour immune setting.