We show that histone deacetylase (HDAC) inhibitors lead to functional expression of MHC class I-related chain A and B (MICA/B) on cancer cells, making them potent targets for natural killer (NK) cell-mediated killing through a NK group 2, member D (NKG2D) restricted mechanism. Blocking either apoptosis or oxidative stress caused by HDAC inhibitor treatment did not affect MICA/B expression, suggesting involvement of a separate signal pathway not directly coupled to induction of cell death. HDAC inhibitor treatment induced glycogen synthase kinase-3 (GSK-3) activity and down-regulation of GSK-3 by small interfering RNA or by different inhibitors showed that GSK-3 activity is essential for the induced MICA/B expression. We thus present evidence that cancer cells which survive the direct induction of cell death by HDAC inhibitors become targets for NKG2D-expressing cells like NK cells, gammadelta T cells, and CD8 T cells.