Background: Prostate cancer patients with pelvic lymph node metastasis (PLNM) have poor prognosis. Based on EAU guidelines, patients with >5% risk of PLNM by nomograms often receive pelvic lymph node dissection (PLND) during prostatectomy. However, nomograms have limited accuracy, so large numbers of false positive patients receive unnecessary surgery with potentially serious side effects. It is important to accurately identify PLNM, yet current tests, including imaging tools are inaccurate. Therefore, we intended to develop a gene expression-based algorithm for detecting PLNM. Methods: An advanced random forest machine learning algorithm screening was conducted to develop a classifier for identifying PLNM using urine samples collected from a multi-center retrospective cohort (n = 413) as training set and validated in an independent multi-center prospective cohort (n = 243). Univariate and multivariate discriminant analyses were performed to measure the ability of the algorithm classifier to detect PLNM and compare it with the Memorial Sloan Kettering Cancer Center (MSKCC) nomogram score. Results: An algorithm named 25 G PLNM-Score was developed and found to accurately distinguish PLNM and non-PLNM with AUC of 0.93 (95% CI: 0.85-1.01) and 0.93 (95% CI: 0.87-0.99) in the retrospective and prospective urine cohorts respectively. Kaplan-Meier plots showed large and significant difference in biochemical recurrence-free survival and distant metastasis-free survival in the patients stratified by the 25 G PLNM-Score (log rank P < 0.001 and P < 0.0001, respectively). It spared 96% and 80% of unnecessary PLND with only 0.51% and 1% of PLNM missing in the retrospective and prospective cohorts respectively. In contrast, the MSKCC score only spared 15% of PLND with 0% of PLNM missing. Conclusions: The novel 25 G PLNM-Score is the first highly accurate and non-invasive machine learning algorithm-based urine test to identify PLNM before PLND, with potential clinical benefits of avoiding unnecessary PLND and improving treatment decision-making.