Purpose In recurrent prostate carcinoma, determination of the site of recurrence is crucial to guide personalized therapy. In contrast to prostate-specific membrane antigen (PSMA)-positron emission tomography (PET) imaging, computed tomography (CT) has only limited capacity to detect lymph node metastases (LNM). We sought to develop a CT-based radiomic model to predict LNM status using a PSMA radioguided surgery (RGS) cohort with histological confirmation of all suspected lymph nodes (LNs). Methods Eighty patients that received RGS for resection of PSMA PET/CT-positive LNMs were analyzed. Forty-seven patients (87 LNs) that received inhouse imaging were used as training cohort. Thirty-three patients (62 LNs) that received external imaging were used as testing cohort. As gold standard, histological confirmation was available for all LNs. After preprocessing, 156 radiomic features analyzing texture, shape, intensity, and local binary patterns (LBP) were extracted. The least absolute shrinkage and selection operator (radiomic models) and logistic regression (conventional parameters) were used for modeling. Results Texture and shape features were largely correlated to LN volume. A combined radiomic model achieved the best predictive performance with a testing-AUC of 0.95. LBP features showed the highest contribution to model performance. This model significantly outperformed all conventional CT parameters including LN short diameter (AUC 0.84), LN volume (AUC 0.80), and an expert rating (AUC 0.67). In lymph node-specific decision curve analysis, there was a clinical net benefit above LN short diameter. Conclusion The best radiomic model outperformed conventional measures for detection of LNM demonstrating an incremental value of radiomic features.