Cancer immunosurveillance eradicates certain neoplasms, but the selective pressure exerted by this active surveillance leads to the emergence of immune evasive tumor clones in a process called cancer immunoediting. Natural killer (NK) cells are potent effectors of cancer immunoediting and can destroy tumors directly via exocytosis of cytotoxic granules or indirectly by producing interferon γ to activate M1 and TH1 immune responses. This review gathers current knowledge of NK immunosurveillance of primary tumors induced in mice and highlights the importance of NK immunosurveillance for human cancers. Evidence of NK immunoediting, as revealed by studies using NK-deficient models, demonstrates how exposure to NK cells engenders modification of cancer immunogenicity to permit survival and progression of the tumor clone in an immunocompetent environment.