Natural killer (NK) cells, which are innate lymphocytes endowed with potent cytotoxic activity, have recently attracted attention as potential anticancer therapeutics. While NK cells mediate encouraging responses in patients with leukemia, the therapeutic effects of NK cell infusion in patients with solid tumors are limited. Preclinical and clinical data suggest that the efficacy of NK cell infusion against solid malignancies is hampered by several factors including inadequate tumor infiltration and persistence/activation in the tumor microenvironment (TME). A number of metabolic features of the TME including hypoxia as well as elevated levels of adenosine, reactive oxygen species, and prostaglandins negatively affect NK cell activity. Moreover, cancer-associated fibroblasts, tumor-associated macrophages, myeloid-derived suppressor cells, and regulatory T cells actively suppress NK cell-dependent anticancer immunity. Here, we review the metabolic and cellular barriers that inhibit NK cells in solid neoplasms as we discuss potential strategies to circumvent such obstacles towards superior therapeutic activity.