In the search for a cure for HIV-1 infection, histone deacetylase inhibitors (HDACi) are being investigated as activators of latently infected CD4 T cells to promote their targeting by cytotoxic T-lymphocytes (CTL). However, HDACi may also inhibit CTL function, suggesting different immunotherapy approaches may need to be explored. Here, we study the impact of different HDACi on both Natural Killer (NK) and CTL targeting of HIV-1 infected cells. We found HDACi down-regulated HLA class I expression independently of HIV-1 Nef which, without significantly compromising CTL function, led to enhanced targeting by NK cells. HDACi-treated HIV-1-infected CD4 T cells were also more effectively cleared than untreated controls during NK co-culture. However, HDACi impaired NK function, reducing degranulation and killing capacity. Depending on the HDACi and dose, this impairment could counteract the benefit gained by treating infected target cells. These data suggest that following HDACi-induced HLA class I down-regulation NK cells kill HIV-1-infected cells, although HDACi-mediated NK cell inhibition may negate this effect. Our data emphasize the importance of studying the effects of potential interventions on both targets and effectors.