miRNAs are predicted to control the activity of approximately 60% of all protein-coding genes participating in the regulation of several cellular processes and diseases, including cancer. Recently, we have demonstrated that miR-187 is significantly downregulated in prostate cancer (PCa) and here we propose a proteomic approach to identify its potential targets. For this purpose, PC-3 cells were transiently transfected with miR-187 precursor and miRNA mimic negative control. Proteins were analyzed by a two-dimensional difference gel electrophoresis (2D-DIGE) and defined as differentially regulated if the observed fold change was ±1.06. Then, MALDI-TOF MS analysis was performed after protein digestion and low abundance proteins were identified by LC-MS/MS. Peptides were identified by searching against the Expasy SWISS PROT database, and target validation was performed both in vitro by western blot and qRT-PCR and in clinical samples by qRT-PCR, immunohistochemistry and ELISA. DIGE analysis showed 9 differentially expressed spots (p<0.05) and 7 showed a down-regulated expression upon miR-187 re-introduction. Among these targets we identified aldehyde dehydrogenase 1A3 (ALDH1A3). ALDH1A3 expression was significantly downregulated in PC3, LNCaP and DU-145 cells after miR-187 re-introduction. Supporting these data, the expression of ALDH1A3 was found significantly (p<0.0001) up-regulated in PCa samples and inversely correlated (p<0.0001) with miR-187 expression, its expression being directly associated with Gleason score (p = 0.05). The expression of ALDH1A3 was measured in urine samples to evaluate the predictive capability of this biomarker for the presence of PCa and, at a signification level of 10%, PSA and also ALDH1A3 were significantly associated with a positive biopsy of PCa. In conclusion, our data illustrate for the first time the role of ALDH1A3 as a miR-187 target in PCa and provide insights in the utility of using this protein as a new biomarker for PCa.