AbstractProstate cancer (PCa) is a tumor with a great heterogeneity, both at a molecular and clinical level. Despite its global good prognosis, cases can vary from indolent to lethal metastatic and scientific efforts are aimed to discern those with worse outcomes. Current prognostic markers, as Gleason score, fall short when it comes to distinguishing these cases. Identification of new early biomarkers to enable a better PCa distinction and classification remains a challenge. In order to identify new genes implicated in PCa progression we conducted several differential gene expression analyses over paired samples comparing primary PCa tissue against healthy prostatic tissue of PCa patients. The results obtained show that this approach is a serious alternative to overcome patient heterogeneity. We were able to identify 250 genes whose expression varies along with tissue differentiation—healthy to tumor tissue, 161 of these genes are described here for the first time to be related to PCa. The further manual curation of these genes allowed to annotate 39 genes with antitumoral activity, 22 of them described for the first time to be related to PCa proliferation and metastasis. These findings could be replicated in different cohorts for most genes. Results obtained considering paired differential expression, functional annotation and replication results point to: CGREF1, UNC5A, C16orf74, LGR6, IGSF1, QPRT and CA14 as possible new early markers in PCa. These genes may prevent the progression of the disease and their expression should be studied in patients with different outcomes.