The aim of the study was to correlate nuclear matrix (NM) protein expression profiles with the risk of PSA progression or death in early prostate cancer (PCa).High-resolution two-dimensional gel electrophoresis (2D-PAGE) was used to identify tumor-associated NM proteins in the PCa specimens obtained from 94 patients. The association between the expression of each protein and the probability of PSA progression or death was studied through univariate analysis. Unsupervised hierarchical clustering analysis was then used to generate patient clusters showing comparable outcomes by including the proteins that were predictive at univariate analysis. PSA-free and overall survival curves relative to each cluster were constructed by means of the Kaplan-Meier method and curves compared by the log-rank test. Multi-parametric models were constructed according to Cox proportional hazard technique.After a median follow-up of 11.7 years (range, 6.5-16.2), 50 patients progressed and 22 died. Of the eight NM proteins identified through 2D-PAGE, proteins NM-6, NM-7 and NM-8 were confirmed to be individually associated with a higher risk of PSA progression at univariate analysis. Proteins NM-6 and NM-8 were also predictive of survival probability. Hierarchical clustering analysis of these proteins allowed to identify one cluster of tumors co-expressing the three proteins or proteins NM-6 and NM-8, characterized by a very poor outcome, suggesting a specific role for these proteins in PCa progression. The predictive value of this mini-signature in respect to PSA-free survival was confirmed by multivariate analysis.Changes in NM scaffolding are strongly associated with the clinical outcome of patients following radical prostatectomy.