Since highly active antiretroviral therapy (HAART) was introduced a decade ago, it has been shown to be effective in keeping HIV-1 replication under control. Nevertheless, it is also known that HAART has certain limitations, such as its inability to completely inhibit the viral replication that maintains virus reservoirs, its high toxicity when the treatment is maintained for long periods of time, and the appearance of viral resistance to the therapy. These limitations have led to the introduction of structured treatment interruption (STI) of antiretroviral therapy, the principle of which is to reduce the clinical complications of HAART, and hypothetically to boost the cellular immune response of the patient host. The aim of this study was to analyze for the first time the impact of STI on the innate immune system. Specifically, we analyzed NK cells and their regulatory receptors (KIRs, NKG2, NCRs, and ILTs) and the cytokines that might control the NK response. Six months after the initiation of STI, the results revealed in most patients a significant increase in NK cells expressing ILT2 and NKp46 receptors. Slight or no changes were observed in other parameters studied, either during interruption or when HAART was reintroduced. Our data show that the STI strategy, irrespective of whether it improved the patients' clinical evolution, induced functional phenotype changes in NK cell subsets.