A differential quantitative protein expression study, comparing matched prostate cancerous and benign tissues from 31 patients, revealed proteins newly associated with prostate cancer. Average effects for 17 proteins whose abundance was significantly different (p<0.01) across patients ranged from 1.5- to 6.1-fold, and included a number of known cancer markers. The most differentially abundant proteins between cancer and benign samples were isopeptidase T, serum amyloid P (SAP), annexin A3 (ANXA3) and mitochondrial enoyl coenzyme-A hydratase. SAP is restricted to stroma in healthy tissue, and the lower abundance in tumours may be explained by the reduced stromal content. ANXA3 is present in healthy epithelial cells, exhibits strong staining in precancerous prostatic intraepithelial neoplasia, and is relatively less abundant in individual tumour cells of increasing Gleason pattern (GP), despite exhibiting higher overall tissue abundance in tumours. ANXA3 staining was predominantly cytoplasmic, yet nuclear localization was also observed. Strongly staining single cells, possibly phagocytes, were interspersed in highly dedifferentiated GP5 tumour areas among tumour cells without measurable ANXA3. Local recurrent androgen ablation therapy-resistant tumours exhibit heterogenous low levels of ANXA3 staining. Results are discussed focussing on the potential implications for tumour tissues.