Natural killer (NK) cells are innate lymphoid cells (ILC) known for their ability to recognize and rapidly eliminate infected or transformed cells. Consequently, NK cells are fundamental for host protection against virus infections and malignancies. Even though the critical role of NK cells in cancer immunosurveillance was suspected years ago, the underlying mechanisms took time to be unraveled. Today, it is clear that anti-tumor functions of NK cells are tightly regulated and expand far beyond the simple killing of malignant cells. In spite of tremendous steps made in understanding the NK cell biology, further work is warranted to fully exploit the anticancer potential of these cells. Indeed, tumor-mediated immune suppression hampers NK cell activity, thus complicating their stimulation for therapeutic purposes. Herein, we review the current knowledge of NK cell functions in anti-tumor immunity . We discuss NK cell activity in the cancer immunoediting process with particular emphasis on the elimination and escape phases.