Background Prostate cancer (PCa) is the most commonly diagnosed malignancy in men who are especially over the age of 50 years in the western countries. Currently used therapeutic modalities mostly fail to give positive clinical outcomes and nearly 30% of the PCa patients eventually develop clinical recurrence. Therefore, understanding the underlying mechanisms of PCa progression is of paramount importance to help determining the course of disease. In this study, we aimed at profiling the differentially expressed microRNAs in recurrent PCa samples. Methods We profiled the microRNA expression of 20 recurrent and 20 non-recurrent PCa patients with microRNA microarray, and validated the differential expression of significantly deregulated microRNAs in 40 recurrent and 39 non-recurrent PCa specimens using quantitative reverse-transcription PCR (qRT-PCR). Data were statistically analyzed using two-sided Student's t-test, Pearson Correlation test, Receiver operating characteristic (ROC) analysis. Results Our results demonstrated that a total of 682 probes were significantly deregulated in recurrent versus non-recurrent PCa specimen comparison. Among those, we confirmed the significant downregulation of miR-424 and upregulation of miR-572 with further qRT-PCR analysis in a larger sample set. Further ROC analysis showed that these microRNAs have enough power to distinguish recurrent specimens from non-recurrent ones on their own. Conclusions Here, we report that differential expression of miR-424 and miR-572 in recurrent PCa specimens can serve as novel biomarkers for prediction of PCa progression.