Background The identification of a blood-based diagnostic marker is a goal in many areas of medicine, including the early diagnosis of prostate cancer. We describe the use of averaged differential display as an efficient mechanism for biomarker discovery in whole blood RNA. The process of averaging reduces the problem of clinical heterogeneity while simultaneously minimizing sample handling. Methodology/Principal Findings RNA was isolated from the blood of prostate cancer patients and healthy controls. Samples were pooled and subjected to the averaged differential display process. Transcripts present at different levels between patients and controls were purified and sequenced for identification. Transcript levels in the blood of prostate cancer patients and controls were verified by quantitative RT-PCR. Means were compared using a t-test and a receiver-operating curve was generated. The Ring finger protein 19A (RNF19A) transcript was identified as having higher levels in prostate cancer patients compared to healthy men through the averaged differential display process. Quantitative RT-PCR analysis confirmed a more than 2-fold higher level of RNF19A mRNA levels in the blood of patients with prostate cancer than in healthy controls (p = 0.0066). The accuracy of distinguishing cancer patients from healthy men using RNF19A mRNA levels in blood as determined by the area under the receiving operator curve was 0.727. Conclusions/Significance Averaged differential display offers a simplified approach for the comprehensive screening of body fluids, such as blood, to identify biomarkers in patients with prostate cancer. Furthermore, this proof-of-concept study warrants further analysis of RNF19A as a clinically relevant biomarker for prostate cancer detection.