Dysfunctional telomeres suppress tumour progression by activating cell-intrinsic programs that lead to growth arrest. Increased levels of TRF2, a key factor in telomere protection, are observed in various human malignancies and contribute to oncogenesis. We demonstrate here that a high level of TRF2 in tumour cells decreased their ability to recruit and activate natural killer (NK) cells. Conversely, a reduced dose of TRF2 enabled tumour cells to be more easily eliminated by NK cells. Consistent with these results, a progressive upregulation of TRF2 correlated with decreased NK cell density during the early development of human colon cancer. By screening for TRF2-bound genes, we found that HS3ST4--a gene encoding for the heparan sulphate (glucosamine) 3-O-sulphotransferase 4--was regulated by TRF2 and inhibited the recruitment of NK cells in an epistatic relationship with TRF2. Overall, these results reveal a TRF2-dependent pathway that is tumour-cell extrinsic and regulates NK cell immunity.