Background: Prostate cancer (PCa) is a prevalent malignancy among elderly men. Biochemical recurrence (BCR), which typically occurs after radical treatments such as radical prostatectomy or radiation therapy, serves as a critical indicator of potential disease progression. However, reliable and effective methods for predicting BCR in PCa patients remain limited. Methods: In this study, we used Bayesian deconvolution combined with 10 machine learning algorithms to build a five-gene model for predicting PCa progression. The model and the five selected genes were externally validated. Various analyses such as prognosis, clinical subgroups, tumor microenvironment, immunity, genetic variants, and drug sensitivity were performed on MSMB/Epithelial_cells subgroups. Results: Our model outperformed 102 previously published prognostic features. Notably, PCa patients with a high proportion of MSMB/epithelial cells were characterized by a greater progression-free Interval (PFI), a higher proportion of early-stage tumors, a lower stromal component, and a reduced presence of tumor-associated fibroblasts (CAF). The high proportion of MSMB/epithelial cells was also associated with higher frequencies of SPOP and TP53 mutations. Drug sensitivity analysis revealed that patients with a poorer prognosis and lower MSMB/epithelial cell ratio showed increased sensitivity to cyclophosphamide, cisplatin, and dasatinib. Conclusions: The model developed in this study provides a robust and accurate tool for predicting PCa progression. It offers significant potential for enhancing risk stratification and informing personalized treatment strategies for PCa patients.