Androgen receptor signaling plays a critical role in prostate cancer pathogenesis. Yet, the regulation of androgen receptor signaling remains elusive. Even with stringent androgen deprivation therapy, androgen receptor signaling persists. Here, our data suggest that there is a complex interaction between the expression of the tumor suppressor miRNA, miR-31, and androgen receptor signaling. We examined primary and metastatic prostate cancer and found that miR-31 expression was reduced as a result of promoter hypermethylation, and importantly, the levels of miR-31 expression were inversely correlated with the aggressiveness of the disease. As the expression of androgen receptor and miR-31 was inversely correlated in the cell lines, our study further suggested that miR-31 and androgen receptor could mutually repress each other. Upregulation of miR-31 effectively suppressed androgen receptor expression through multiple mechanisms and inhibited prostate cancer growth in vivo. Notably, we found that miR-31 targeted androgen receptor directly at a site located in the coding region, which was commonly mutated in prostate cancer. In addition, miR-31 suppressed cell-cycle regulators including E2F1, E2F2, EXO1, FOXM1, and MCM2. Together, our findings suggest a novel androgen receptor regulatory mechanism mediated through miR-31 expression. The downregulation of miR-31 may disrupt cellular homeostasis and contribute to the evolution and progression of prostate cancer. We provide implications for epigenetic treatment and support clinical development of detecting miR-31 promoter methylation as a novel biomarker.