The androgen receptor (AR) is a key molecule involved in prostate cancer (PC) development and progression. Post-translational modification of the AR by co-regulator proteins can modulate its transcriptional activity. To identify which demethylases might be involved in AR regulation, an siRNA screen was performed to reveal that the demethylase, KDM4B, may be an important co-regulator protein. KDM4B enzymatic activity is required to enhance AR transcriptional activity; however, independently of this activity, KDM4B can enhance AR protein stability via inhibition of AR ubiquitination. Importantly, knockdown of KDM4B in multiple cell lines results in almost complete depletion of AR protein levels. For the first time, we have identified KDM4B to be an androgen-regulated demethylase enzyme, which can influence AR transcriptional activity not only via demethylation activity but also via modulation of ubiquitination. Together, these findings demonstrate the close functional relationship between AR and KDM4B, which work together to amplify the androgen response. Furthermore, KDM4B expression in clinical PC specimens positively correlates with increasing cancer grade (P < 0.001). Consequently, KDM4B is a viable therapeutic target in PC.