During cancer immunoediting, loss of major histocompatibility complex class I (MHC-I) in neoplasm contributes to the evasion of tumours from host immune system. Recent studies have demonstrated that most natural killer (NK) cells that are found in advanced cancers are defective, releasing the malignant MHC-I-deficient tumours from NK-cell-dependent immune control. Here, we show that a natural killer T (NKT)-cell-ligand-loaded tumour-antigen expressing antigen-presenting cell (APC)-based vaccine effectively eradicates these advanced tumours. During this process, we find that the co-expression of Tim-3 and PD-1 marks functionally exhausted NK cells in advanced tumours and that MHC-I downregulation in tumours is closely associated with the induction of NK-cell exhaustion in both tumour-bearing mice and cancer patients. Furthermore, the recovery of NK-cell function by IL-21 is critical for the anti-tumour effects of the vaccine against advanced tumours. These results reveal the process involved in the induction of NK-cell dysfunction in advanced cancers and provide a guidance for the development of strategies for cancer immunotherapy.