The marker currently used for prostate cancer (CaP) detection is an increase in serum prostate-specific antigen (PSA). However, the PSA test which may give false positive or negative information, is not reliable and does not allow the differentiation of benign prostate hyperplasia (BPH), non-aggressive CaP and aggressive CaP. There is thus an urgent need to search for novel CaP biomarkers to improve the early detection and accuracy of diagnosis, determine the aggressiveness of CaP and to monitor the efficacy of treatment. Proteomic techniques allow for a high-throughput analysis of bio-fluids with the visualization and quantification of thousands of potential protein markers and represent very promising tools in the search for new, improved molecular markers of CaP. In this review, we will summarize conventional CaP biomarkers and focus on novel identified biomarkers for CaP early diagnosis and progression that might be used in the future.