Abstract Background Despite recent progress in the identification of genetic and molecular alterations in prostate cancer, markers associated with tumor progression are scarce. Therefore precise diagnosis of patients and prognosis of the disease remain difficult. This study investigated novel molecular markers discriminating between low and highly aggressive types of prostate cancer. Results Using 52 microdissected cell populations of low- and high-risk prostate tumors, we identified via global cDNA microarrays analysis almost 1200 genes being differentially expressed among these groups. These genes were analyzed by statistical, pathway and gene enrichment methods. Twenty selected candidate genes were verified by quantitative real time PCR and immunohistochemistry. In concordance with the mRNA levels, two genes MAP3K5 and PDIA3 exposed differential protein expression. Functional characterization of PDIA3 revealed a pro-apoptotic role of this gene in PC3 prostate cancer cells. Conclusions Our analyses provide deeper insights into the molecular changes occurring during prostate cancer progression. The genes MAP3K5 and PDIA3 are associated with malignant stages of prostate cancer and therefore provide novel potential biomarkers.