The transcriptional activity of the androgen receptor (AR) is regulated by both ligand binding and post-translational modifications, including acetylation and small ubiquitin-like modifier (SUMO)ylation. Histone deacetylases (HDACs) are known to catalyze the removal of acetyl groups from both histones and non-histone proteins. In this study, we report that HDAC4 binds to and inhibits the activity of the AR. This inhibition was found to depend on the SUMOylation, instead of deacetylation, of the AR. Consistently, HDAC4 increases the level of AR SUMOylation in both whole-cell and cell-free assay systems, raising the possibility that the deacetylase may act as an E3 ligase for AR SUMOylation. Knock down of HDAC4 increases the activity of endogenous AR and androgen induction of prostate-specific antigen expression and prostate cancer cell growth, which is associated with decreased SUMOylation of the receptor. Overall, the studies identify HDAC4 as a positive regulator for AR SUMOylation, revealing a deacetylase-independent mechanism of HDAC action in prostate cancer cells.