Prostate carcinoma is the most common cancer of western men and is a markedly heterogeneous disease. The aim of this study was to identify signatures of differentially expressed genes in prostate cancer using DNA microarray technology, evaluating expression profiles in matched pairs of benign and malignant tissue. Samples were collected from 33 radical prostatectomies, and 52 specimens were included, representing 29 histologically verified primary tumours, 19 paired samples of malignant and benign tissue, and 4 non-paired benign tissue samples. Microarray analysis was performed using an expanded sequence verified set of 40,000 human cDNA clones, revealing several genes with significant differences between malignant and benign tissue, including recently reported genes like alpha-methylacyl-CoA racemase (AMACR) and hepsin, as well as genes relevant for tumour development and progression. Leave out cross validation (LOCV) test correctly predicted tumour or benign tissue in 47 (90.3%) out of 52 cases, significantly better than cross validation tests using randomly permuted tissue labels. Unsupervised clustering analysis revealed 3 distinct patient clusters significantly associated with Gleason score, and high grade tumours (Gleason score >/=7) accumulated in cluster 1 (C1). Gene expression profiles correctly predicted 100% of tumour samples segregating to C1, as also validated by LOCV. Gene expression profiles were analysed in filtered and floored datasets with similar results, and a pair-wise design was also tested. Gene expression profiles provided tumour clusters linked to differentiation, and revealed novel markers relevant for molecular classification, grading and therapy of prostate cancer.