Posttranslational modifications of histones, such as methylation, regulate chromatin structure and gene expression. Recently, lysine-specific demethylase 1 (LSD1), the first histone demethylase, was identified. LSD1 interacts with the androgen receptor and promotes androgen-dependent transcription of target genes by ligand-induced demethylation of mono- and dimethylated histone H3 at Lys 9 (H3K9) only. Here, we identify the Jumonji C (JMJC) domain-containing protein JMJD2C as the first histone tridemethylase regulating androgen receptor function. JMJD2C interacts with androgen receptor in vitro and in vivo. Assembly of ligand-bound androgen receptor and JMJD2C on androgen receptor-target genes results in demethylation of trimethyl H3K9 and in stimulation of androgen receptor-dependent transcription. Conversely, knockdown of JMJD2C inhibits androgen-induced removal of trimethyl H3K9, transcriptional activation and tumour cell proliferation. Importantly, JMJD2C colocalizes with androgen receptor and LSD1 in normal prostate and in prostate carcinomas. JMJD2C and LSD1 interact and both demethylases cooperatively stimulate androgen receptor-dependent gene transcription. In addition, androgen receptor, JMJD2C and LSD1 assemble on chromatin to remove methyl groups from mono, di and trimethylated H3K9. Thus, our data suggest that specific gene regulation requires the assembly and coordinate action of demethylases with distinct substrate specificities.