We show that HEXIM1 (hexamethylene bis-acetamide inducible 1) functions as an AR (androgen receptor) co-repressor as it physically interacts with the AR and is required for the ability of anti-androgens to inhibit androgen-induced target gene expression and cell proliferation. Oncomine™ database and IHC (immunohistochemistry) analyses of human prostate tissues revealed that expression of HEXIM1 mRNA and protein are down-regulated during the development and progression of prostate cancer. Enforced down-regulation of HEXIM1 in parental hormone-dependent LNCaP cells results in resistance to the inhibitory action of anti-androgens. Conversely, ectopic expression of HEXIM1 in the CRPC (castration-resistant prostate cancer) cell line, C4-2, enhances their sensitivity to the repressive effects of the anti-androgen bicalutamide. Novel insight into the mechanistic basis for HEXIM1 inhibition of AR activity is provided by the present studies showing that HEXIM1 induces expression of the histone demethylase KDM5B (lysine-specific demethylase 5B) and inhibits histone methylation, resulting in the inhibition of FOXA1 (forkhead box A1) licensing activity. This is a new mechanism of action attributed to HEXIM1, and distinct from what has been reported so far to be involved in HEXIM1 regulation of other nuclear hormone receptors, including the oestrogen receptor.