Within five to ten years after radical prostatectomy (RP), approximately 15–34% of prostate cancer (PCa) patients experience biochemical recurrence (BCR), which is defined as recurrence of serum levels of prostate-specific antigen >0.2 µg/L, indicating probable cancer recurrence. Models using clinicopathological variables for predicting this risk for patients lack accuracy. There is hope that new molecular biomarkers, like microRNAs (miRNAs), could be potential candidates to improve risk prediction. Therefore, we evaluated the BCR prognostic capability of 20 miRNAs, which were selected by a systematic literature review. MiRNA expressions were measured in formalin-fixed, paraffin-embedded (FFPE) tissue RP samples of 206 PCa patients by RT-qPCR. Univariate and multivariate Cox regression analyses were performed, to assess the independent prognostic potential of miRNAs. Internal validation was performed, using bootstrapping and the split-sample method. Five miRNAs (miR-30c-5p/31-5p/141-3p/148a-3p/miR-221-3p) were finally validated as independent prognostic biomarkers. Their prognostic ability and accuracy were evaluated using C-statistics of the obtained prognostic indices in the Cox regression, time-dependent receiver-operating characteristics, and decision curve analyses. Models of miRNAs, combined with relevant clinicopathological factors, were built. The five-miRNA-panel outperformed clinically established BCR scoring systems, while their combination significantly improved predictive power, based on clinicopathological factors alone. We conclude that this miRNA-based-predictor panel will be worth to be including in future studies.