Androgen receptor (AR) has essential roles during prostate cancer progression. With genome-wide AR-binding sites mapped to high resolution, studies have recently reported AR as a transcriptional repressor. How AR inhibits gene expression and how this contributes to prostate cancer, however, are incompletely understood. Through meta-analysis of microarray data, here we nominate nephroblastoma overexpressed (NOV) as a top androgen-repressed gene. We show that NOV is directly suppressed by androgen through the AR. AR occupies the NOV enhancer and communicates with the NOV promoter through DNA looping. AR activation recruits the polycomb group protein EZH2, which subsequently catalyzes histone H3 lysine 27 tri-methylation around the NOV promoter, thus leading to repressive chromatin remodeling and epigenetic silencing. Concordantly, AR and EZH2 inhibition synergistically restored NOV expression. NOV is downregulated in human prostate cancer wherein AR and EZH2 are upregulated. Functionally, NOV inhibits prostate cancer cell growth in vitro and in vivo. NOV reconstitution reverses androgen-induced cell growth and NOV knockdown drives androgen-independent cell growth. In addition, NOV expression is restored by hormone-deprivation therapies in mice and prostate cancer patients. Therefore, using NOV as a model gene we gained further understanding of the mechanisms underlying AR-mediated transcriptional repression. Our findings establish a tumor-suppressive role of NOV in prostate cancer and suggest that one important, but previously underestimated, manner by which AR contributes to prostate cancer progression is through inhibition of key tumor-suppressor genes.