MicroRNAs are important epigenetic regulators of protein expression by triggering degradation of target mRNAs and/or inhibiting their translation. Dysregulation of microRNA expression has been reported in several cancers, including prostate cancer (PC). We comprehensively characterized the proteomic footprint of a panel of 12 microRNAs that are potently suppressed in metastatic PC (SiM-miRNAs: miR-1, miR-133a, miR-133b, miR-135a, miR-143-3p, miR-145-3p, miR-205, miR-221-3p, miR-221-5p, miR-222-3p, miR-24-1-5p, and miR-31) using reverse-phase proteomic arrays. Re-expression of these SiM-miRNAs in PC cells suppressed cell proliferation and targeted key oncogenic pathways, including cell cycle, apoptosis, Akt/mammalian target of rapamycin signaling, metastasis and the androgen receptor (AR) axis. However, only 12%, at most, of these observed protein expression changes could be explained by predicted direct binding of miRNAs to corresponding mRNAs, suggesting that the majority of these proteomic effects result indirectly. AR and its steroid receptor coactivators (SRCs; SRC-1, -2 and -3) were recurrently affected by these SiM-miRNAs. In agreement, we identified inverse correlations between expression of these SiM-miRNAs and early clinical recurrence, as well as with AR transcriptional activity in human PC tissues. We also identified robust induction of miR-135a by androgen and strong direct binding of AR to the miR-135a locus. As miR-135a potently suppresses AR expression, this results in a negative feedback loop that suppresses AR protein expression in an androgen-dependent manner, while de-repressing AR expression upon androgen deprivation. Our results demonstrate that epigenetic silencing of these SiM-miRNAs can result in increased AR axis activity and cell proliferation, thus contributing to disease progression. We further demonstrate that a negative feedback loop involving miR-135a can restore AR expression under androgen-deprivation conditions, thus contributing to the upregulation of AR protein expression in castration-resistant PC. Finally, our unbiased proteomic profiling demonstrates that the majority of actual protein expression changes induced by SiM-miRNAs cannot be explained based on predicted direct interactions.