Depression is a prevalent and debilitating psychiatric illnesses. However, currently prescribed antidepressant drugs are only efficacious in a limited group of patients. Studies on Balb/c mice suggested that histone deacetylase (HDAC) inhibition may enhance the efficacy of the widely-prescribed antidepressant drug fluoxetine. This study shows that reducing HDAC activity in fluoxetine-treated Balb/c mice leads to robust antidepressant and anxiolytic effects. While reducing the activity of class I HDACs 1 and 3 led to antidepressant effects, additional class II HDAC inhibition was necessary to exert anxiolytic effects. In fluoxetine-treated mice, HDAC inhibitors increased enrichment of acetylated histone H4 protein and RNA polymerase II at promotor 3 of the brain-derived neurotrophic factor (Bdnf) gene and increased Bdnf transcription from this promotor. Reducing Bdnf-stimulated tropomyosin kinase B receptor activation in fluoxetine-treated mice with low HDAC activity abolished the behavioral effects of fluoxetine, suggesting that the HDAC-triggered epigenetic stimulation of Bdnf expression is critical for therapeutic efficacy.