Prostate cancer (PCa) is currently the most frequently diagnosed malignancy in the western countries. It is more prevalent in older men with 75% of the incident cases above 65 years old. After radical prostatectomy, approximately 30% of men develop clinical recurrence with elevated serum prostate-specific antigen levels. Therefore, it is important to unravel the molecular mechanisms underlying PCa progression to develop novel diagnostic/therapeutic approaches. In this study, it is aimed to compare the microRNA (miRNA) profile of recurrent and non-recurrent prostate tumor tissues to explore the possible involvement of miRNAs in PCa progression. Total RNA from 41 recurrent and 41 non-recurrent PCa tissue samples were used to investigate the miRNA signature in PCa specimens. First of all, 20 recurrent and 20 non-recurrent PCa samples were profiled using miRNA microarray chips. Of the differentially expressed miRNAs, miR-1, miR-133b and miR-145* were selected for further validation with qRT-PCR in a different set of 21 recurrent and 21 non-recurrent PCa samples. Data were statistically analyzed using two-sided Student's t-test, Pearson Correlation test, Receiver operating characteristic analysis. Our results demonstrated that miR-1 and mir-133b have been significantly downregulated in recurrent PCa specimens in comparison to non-recurrent PCa samples and have sufficient power to distinguish recurrent specimens from non-recurrent ones on their own. Here, we report that the relative expression of miR-1 and mir-133b have been significantly reduced in recurrent PCa specimens in comparison to non-recurrent PCa samples, which can serve as novel biomarkers for prediction of PCa progression.