Elevated levels of androgen receptor (AR) in prostate cancer confer resistance to current antiandrogens and play a causal role in disease progression due to persistent target gene activation. Through pharmacologic and genetic approaches, we show that half of all direct AR target genes, including TMPRSS2, the primary driver of ETS fusion transcripts in 70 percent of human prostate cancers, require histone deacetylase (HDAC) activity for transcriptional activation by AR. Surprisingly, the HDAC3-NCoR complex, which typically functions to repress gene expression by nuclear receptors, is required for AR target gene activation. Prostate cancer cells treated with HDAC inhibitors have reduced AR protein levels, but we show that the mechanism of blockade of AR activity is through failure to assemble a coactivator/RNA polymerase II complex after AR binds to the enhancers of target genes. Failed complex assembly is associated with a phase shift in the cyclical wave of AR recruitment that typically occurs in response to ligand treatment. HDAC inhibitors retain the ability to block AR activity in hormone refractory prostate cancer models and therefore merit clinical investigation in this setting. HDAC-regulated AR target genes defined here can serve as biomarkers to ensure sufficient levels of HDAC inhibition.