Prostate-specific membrane antigen (PSMA) positron emission tomography (PET)/computed tomography (CT) is an emerging imaging modality with greater sensitivity and specificity over conventional imaging for prostate cancer (PCa) staging. Using data from two prospective trials (NCT03368547 and NCT04050215), we explored predictors of overall upstaging (nodal and metastatic) by PSMA PET/CT among patients with cN0M0 National Comprehensive Cancer Network high-risk PCa on conventional imaging (n = 213). Overall, 21.1%, 8.9%, and 23.9% of patients experienced nodal, metastatic, and overall upstaging, respectively, without histologic confirmation. On multivariable analysis, Gleason grade group (GG) and percent positive core (PPC) on systematic biopsy significantly predict overall upstaging (odds ratio [OR] 2.15, 95% confidence interval [CI] 1.33–3.45; p = 0.002; and OR 1.03, 95% CI 1.01–1.04; p < 0.001). Overall upstaging was significantly more frequent among men with GG 5 disease (33.0% vs. 17.6%; p = 0.0097) and PPC ≥50% (33.0% vs 15.0%; p = 0.0020). We constructed a nomogram that predicts overall upstaging using initial prostate-specific antigen, PPC, GG, and cT stage, with coefficients estimated from a standard logistic regression model (using maximum likelihood estimation). It is internally validated with a tenfold cross-validated area under the receiver operating characteristic curve estimated at 0.74 (95% CI 0.67–0.82). In our cohort, 90% of patients who had a nomogram-estimated risk below the cutoff of 22% for overall upstaging could have been spared PSMA PET/CT as our model correctly predicted no upstaging. In other words, the predictive model only missed 10% of patients who would otherwise have benefitted from PSMA PET/CT.