Natural killer (NK) cells belong to the innate immune system and are potent cytolytic and cytokine-producing effector cells in response to tumor targets. NK cell based anti-tumor immunotherapy was so far mainly successful in patients with different types of leukemia. For instance, acute myeloid leukemia (AML) patients displayed a prolonged survival if transplanted with haploidentical stem cells giving rise to NK cells with a mismatch in inhibitory killer immunoglobulin receptors (KIRs) and recipients' HLA class I. Although promising results have been achieved with hematological tumors, solid tumors are in most cases poorly controlled by NK cells. Therapeutic protocols that aimed at improving NK cell responses in patients with solid malignancies succeeded in increasing NK cell numbers and functional responses of NK cells isolated from the patients' peripheral blood. However, in the majority of cases tumor progression and overall survival of patients were not significantly improved. There is increasing evidence that tumor-associated NK cells become gradually impaired during tumor progression compared to NK cells from peripheral blood and healthy tissues. Future protocols of NK cell based immunotherapy should integrate three important aspects to improve NK cell anti-tumor activity: facilitating NK cell migration to the tumor site, enhancing their infiltration into the tumor tissue and ensuring subsequent efficient activation in the tumor. This review summarizes the current knowledge of tumor-infiltrating NK cells and the influence of the tumor microenvironment on their phenotype and function.