Following radical surgery, patients may suffer a relapse. It is important to identify such patients so that therapy tactics can be modified appropriately. Existing stratification schemes do not display the probability of recurrence with enough precision since locally advanced prostate cancer (PCa) is classified as high-risk but is not ranked in greater detail. Between 40 and 50% of PCa cases belong to the TMPRSS2-ERG subtype that is a sufficiently homogeneous group for high-precision prognostic marker search to be possible. This study includes two independent cohorts and is based on high throughput sequencing and qPCR data. As a result, we have been able to suggest a perspective-trained model involving a deep neural network based on both qPCR data for mRNA and miRNA and clinicopathological criteria that can be used for recurrence risk forecasts in patients with TMPRSS2-ERG-positive, locally advanced PCa (the model uses ALDH3A2 + ODF2 + QSOX2 + hsa-miR-503-5p + ISUP + pT, with an AUC = 0.944). In addition to the prognostic model’s use of identified differentially expressed genes and miRNAs, miRNA–target pairs were found that correlate with the prognosis and can be presented as an interactome network.