Natural Killer (NK) cells belong to a unique subtype of lymphocytes with a great potential for cancer immunotherapy due to their ability to rapidly recognize and efficiently kill tumor cells. Their anti-cancer potential can be further increased by genetic and non-genetic modifications. However, the attempts of genetic improvements of NK cells over the past 20 years have been hampered by the difficulties of gene delivery into this cell type, thus preventing researchers from producing clinically relevant numbers of viable and biologically active NK cells. Currently, several successful approaches to genetic modification of NK cells have been described, and clinically applicable cell therapy products have been characterized. Now that we understand much better the ways of NK cell optimization to enhance their tumor regression-inducing capabilities, novel approaches to engineering NK surface receptors are being developed. In this review, we focus on the advantages and perspectives of various approaches to modification of NK cells. Positive results of several preclinical studies are described, demonstrating that genetically modified NK cells can be comparable to therapeutic T cells in their efficiency of recognizing and destroying tumor targets. Moreover, using allogenic NK cells to treat a number of cancer types might have even wider and eager clinical adoption than cytotoxic T cells due to a much decreased risk of graft versus host reaction inherent in NK cell-based immunotherapeutic products.