Natural killer (NK) cells represent important early effector cells in innate immune defense as they exert their functions without prior sensitization. They participate in regulation of innate and adaptive immune responses and hematopoiesis by producing various cytokines and chemokines. In addition, NK cells lyse virally infected and malignant cells raising them to multifunctional members of the first line of defense. Unlike other lymphocytes they lack specific antigen receptors. They rather bind cells using ubiquitous molecules and communicate via a pattern of receptors specific for MHC-I molecules with their counterparts. In general, successful binding of the receptors delivers an inhibitory signal to NK cells thus sparing the target cell from lysis. In contrast, down-regulated or altered MHC-I expression as frequently observed during virus infection or on malignant cells prevents ligation of inhibitory receptors and MHC-I paralyzing inhibition and thus inducing lysis of the target cell. In human immunodeficiency virus (HIV) infection NK cells are of central importance since they can combat viral infection itself and opportunistic pathogens like fungi and protozoa that usually spread during the course of HIV infection. However, various studies have reported alterations in HIV patients affecting NK cell numbers and functions that might negatively influence course and severity of the disease. This review will focus on the mutual interference of NK cells and the HI virus.