Abstract Background Zyflamend, a mixture containing extracts of ten herbs, has shown promise in a variety of preclinical cancer models, including prostate cancer. The current experiments were designed to investigate the effects of Zyflamend on the expression of class I and II histone deacetylases, a family of enzymes known to be over expressed in a variety of cancers. Methods CWR22Rv1 cells, a castrate-resistant prostate cancer cell line, were treated with Zyflamend and the expression of class I and II histone deacetylases, along with their downstream target the tumor suppressor gene p21, was investigated. Involvement of p21 was confirmed with siRNA knockdown and over expression experiments. Results Zyflamend down-regulated the expression of all class I and II histone deacetylases where Chinese goldthread and baikal skullcap (two of its components) appear to be primarily responsible for these results. In addition, Zyflamend up regulated the histone acetyl transferase complex CBP/p300, potentially contributing to the increase in histone 3 acetylation. Expression of the tumor suppressor gene p21, a known downstream target of histone deacetylases and CBP/p300, was increased by Zyflamend treatment and the effect on p21 was, in part, mediated through Erk1/2. Knockdown of p21 with siRNA technology attenuated Zyflamend-induced growth inhibition. Over expression of p21 inhibited cell growth and concomitant treatment with Zyflamend enhanced this effect. Conclusions Our results suggest that the extracts of this polyherbal combination increase histone 3 acetylation, inhibit the expression of class I and class II histone deacetylases, increase the activation of CBP/p300 and inhibit cell proliferation, in part, by up regulating p21 expression.