Prostate cancer (PCa) is a potentially curable disease when diagnosed in early stages and subsequently treated with radical prostatectomy (RP). However, a significant proportion of patients tend to relapse early, with the emergence of biochemical failure (BF) as an established precursor of progression to metastatic disease. Several candidate molecular markers have been studied in an effort to enhance the accuracy of existing predictive tools regarding the risk of BF after RP. We studied the immunohistochemical expression of p53, cyclooxygenase-2 (COX-2) and cyclin D1 in a cohort of 70 patients that underwent RP for early stage, hormone naïve PCa, with the aim of prospectively identifying any possible interrelations as well as correlations with known prognostic parameters such as Gleason score, pathological stage and time to prostate-specific antigen (PSA) relapse. We observed a significant (p = 0.003) prognostic role of p53, with high protein expression correlating with shorter time to BF (TTBF) in univariate analysis. Both p53 and COX-2 expression were directly associated with cyclin D1 expression (p = 0.055 and p = 0.050 respectively). High p53 expression was also found to be an independent prognostic factor (p = 0.023). Based on previous data and results provided by this study, p53 expression exerts an independent negative prognostic role in localized prostate cancer and could therefore be evaluated as a useful new molecular marker to be added in the set of known prognostic indicators of the disease. With respect to COX-2 and cyclin D1, further studies are required to elucidate their role in early prediction of PCa relapse after RP.