Natural killer (NK) cells as components of the innate immunity substantially contribute to antitumor immune responses. However, the tumor-associated ligands engaging activating NK cell receptors are largely unknown. An exception are the MHC class I chain-related molecules MICA and MICB and the UL16-binding proteins (ULBP) which bind to the activating immunoreceptor NKG2D expressed on cytotoxic lymphocytes. A therapeutic induction of NKG2D ligands that primes cancer cells for NK cell lysis has not yet been achieved. By microarray studies, we found evidence that treatment of human hepatocellular carcinoma cells with the histone deacetylase inhibitor (HDAC-I) sodium valproate (VPA) mediates recognition of cancer cells by cytotoxic lymphocytes via NKG2D. VPA induced transcription of MICA and MICB in hepatocellular carcinoma cells, leading to increased cell surface, soluble and total MIC protein expression. No significant changes in the expression of the NKG2D ligands ULBP1-3 were observed. The induction of MIC molecules increased lysis of hepatocellular carcinoma cells by NK cells which was abolished by addition of a blocking NKG2D antibody. Importantly, in primary human hepatocytes, VPA treatment did not induce MIC protein expression. Taken together, our data show that the HDAC-I VPA mediates specific priming of malignant cells for innate immune effector mechanisms. These results suggest the clinical evaluation of HDAC-I in solid tumors such as hepatocellular carcinoma, especially in combination with immunotherapy approaches employing adoptive NK cell transfer.