Androgen signaling, via the androgen receptor (AR), is crucial in mediating prostate cancer (PCa) initiation and progression. Identifying new downstream effectors of the androgens/AR pathway will allow a better understanding of these mechanisms and could reveal novel biomarkers and/or therapeutic agents to improve the rate of patient survival. We compared the microRNA expression profiles in androgen-sensitive LNCaP cells stimulated or not with 1 nM R1881 by performing a high-throughput reverse transcriptase-quantitative PCR and found that miR-135a was upregulated. After androgen stimulation, we showed that AR directly activates the transcription of miR-135a2 gene by binding to an androgen response element in the promoter region. Our findings identify miR-135a as a novel effector in androgens/AR signaling. Using xenograft experiments in chick embryos and adult male mice, we showed that miR-135a overexpression decreases in vivo invasion abilities of prostate PC-3 cells. Through in vitro wound-healing migration and invasion assays, we demonstrated that this effect is mediated through downregulating ROCK1 and ROCK2 expression, two genes that we characterized as miR-135a direct target genes. In human surgical samples from prostatectomy, we observed that miR-135a expression was lower in tumoral compared with paired adjacent normal tissues, mainly in tumors classified with a high Gleason score (⩾8). Moreover, miR-135a expression is lower in invasive tumors, showing extraprostatic extension, as compared with intraprostatic localized tumors. In tumor relative to normal glands, we also showed a more frequently higher ROCK1 protein expression determined using a semi-quantitative immunohistochemistry analysis. Therefore, in tumor cells, the lower miR-135a expression could lead to a higher ROCK1 protein expression, which could explain their invasion abilities. The highlighted relationship between miR-135a expression level and the degree of disease aggressiveness suggests that miR-135a may be considered as a prognostic marker in human PCa.