During cancer development, tumor suppressor genes were silenced by promoter methylation or histone deacetylation. Histone deacetylases (HDACs) are important to maintain histone deacetylation. HDAC inhibitors (HDACis) were thus proposed as a new therapeutic approach to cancer. The current study aims to understand the effect and molecular mechanisms of HDACis on gastric cancer cells. Trichostatin A (TSA) significantly inhibited the growth of gastric cancer cells by inducing apoptosis. Gene profiling results showed PUMA (p53 upregulated modulator of apoptosis) as one of 122 genes upregulated in TSA-treated gastric cancer cells. PUMA was downregulated in gastric cancer cell lines and primary gastric carcinoma tissues. Patients with low PUMA expression had significant decreases in overall survival (HR, 2.04; p = 0.047). Ectopic PUMA expression inhibited the growth of gastric cancer cells while PUMA depletion promoted cellular growth. The knockdown of HDAC3 but not other HDACs upregulated PUMA expression. HDAC3 could bind to PUMA promoter, which was abrogated after TSA treatment. In contrast to TSA and SB, HDAC3 siRNA failed to upregulate p53 expression but promoted the interaction of p53 with PUMA promoter. In summary, proapoptotic PUMA was downregulated in gastric cancer and its mRNA expression level is a valuable prognosis factor for gastric cancer. HDAC3 is important to downregulate PUMA expression in gastric cancer and HDACis, like TSA, promoted PUMA expression through stabilizing p53 in addition to HDAC3 inhibition. In combination with chemotherapy, targeting HDAC3 might be a promising strategy to induce apoptosis of gastric cancer cells.