Background/Objectives: This study evaluates whether combining ⁶⁸Ga-PSMA-11-PET/CT derived imaging biomarkers with clinical risk factors improves the prediction of early biochemical recurrence (eBCR) or clinical progress in patients with high-risk prostate cancer (PCa) after primary treatment, using machine learning (ML) models. Methods: We analyzed data from 93 high-risk PCa patients who underwent ⁶⁸Ga-PSMA-11 PET/CT and received primary treatment at a single center. Two predictive models were developed: a logistic regression (LR) model and an ML derived probabilistic graphical model (PGM) based on a naïve Bayes framework. Both models were compared against each other and against the CAPRA risk score. The models’ input variables were selected based on statistical analysis and domain expertise including a literature review and expert input. A decision tree was derived from the PGM to translate its probabilistic reasoning into a transparent classifier. Results: The five key input variables were as follows: binarized CAPRA score, maximal intraprostatic PSMA uptake intensity (SUVmax), presence of bone metastases, nodal involvement at common iliac bifurcation, and seminal vesicle infiltration. The PGM achieved superior predictive performance with a balanced accuracy of 0.73, sensitivity of 0.60, and specificity of 0.86, substantially outperforming both the LR (balanced accuracy: 0.50, sensitivity: 0.00, specificity: 1.00) and CAPRA (balanced accuracy: 0.59, sensitivity: 0.20, specificity: 0.99). The decision tree provided an explainable classifier with CAPRA as a primary branch node, followed by SUVmax and specific PET-detected tumor sites. Conclusions: Integrating ⁶⁸Ga-PSMA-11 imaging biomarkers with clinical parameters, such as CAPRA, significantly improves models to predict progression in patients with high-risk PCa undergoing primary treatment. The PGM offers superior balanced accuracy and enables risk stratification that may guide personalized treatment decisions.