Prostate cancer (PCa) is the second-leading cause of cancer death among men in the worldwide. Most PCa is slowly growing and usually early symptomless. About 70% of PCa patients were diagnosed at later stage and metastasis has been observed. Additionally, the cure rate of PCa closely relies on the early diagnosis with biomarkers. Prostatic Specific Antigen (PSA) is currently the only clinical biomarker for PCa diagnosis. However, the PSA test has inherent limitations and has about 75% of false-positive results. The identification of a set of genes (as biomarkers) for diagnosis and prognosis is an urgent clinical issue for PCa. Here, we integrated genome-wide analysis and protein-protein interaction network to identify potential genes for early diagnostic biomarkers of PCa. First, we collected gene expression datasets of 145 PCa samples, consisting of both tumor and corresponding normal tissues, from two different sources in Gene Expression Omnibus (GEO). We found 158 and 268 significantly highly and lowly expressed genes, respectively, in tumor samples. Moreover, we proposed cluster score (CS) and predicting score (PS) to select 28 prostate cancer-related genes (called PCa28). The results indicate that PCa28 can discriminate between the normal/tumor tissues and are specific for prostate cancer. Finally, we examined 8 genes in PCa28 on four PCa cell lines by real time quantitative polymerase chain reaction (RT-qPCR). Experimental results show that up-regulated genes have higher expression level in tumor cells in comparison to normal cells, and down-regulated genes have lower expression level in tumor cells. We believe that our method is useful and PCa28 are potential biomarkers that provide the clues to develop targeting therapy for PCa.