Natural killer (NK) cells were discovered 40 years ago, by their ability to recognize and kill tumor cells without the requirement of prior antigen exposure. Since then NK cells have been seen as promising agents for cell-based cancer therapies. However, NK cells represent only a minor fraction of the human lymphocyte population. Their skewed phenotype and impaired functionality during cancer progression necessitates the development of clinical protocols to activate and expand to high numbers ex vivo to be able to infuse sufficient numbers of functional NK cells to the cancer patients. Initial NK cell-based clinical trials suggested that NK cell-infusion is safe and feasible with almost no NK cell-related toxicity, including graft-versus-host disease (GvHD). Complete remission and increased disease free survival is shown in a small number of patients with hematological malignances. Furthermore, successful adoptive NK cell based therapies from haploidentical donors have been demonstrated. Disappointingly, only limited anti-tumor effects have been demonstrated following NK cell infusion in patients with solid tumors. While NK cells have great potential in targeting tumor cells, the efficiency of NK cell functions in the tumor microenvironment is yet unclear. The failure of immune surveillance may in part be due to sustained immunological pressure on tumor cells resulting in the development of tumor escape variants that are invisible to the immune system. Alternatively, this could be due to the complex network of immune suppressive compartments in the tumor microenvironment, including myeloid-derived suppressor cells, tumor associated macrophages, and regulatory T cells. Although the negative effect of the tumor microenvironment on NK cells can be transiently reverted by ex vivo-expansion and long-term activation, the abovementioned NK cell/tumor microenvironment interactions upon reinfusion are not fully elucidated. Within this context, genetic modification of NK cells may provide new possibilities for developing effective cancer immunotherapies by improving NK cell responses and making them less susceptible to the tumor microenvironment.Within this review we will discuss clinical trials using NK cells with a specific reflection on novel potential strategies, such as genetic modification of NK cells and complementary therapies aimed at improving the clinical outcome of NK cell-based immune therapies.