Prostate cancer is the most common noncutaneous malignant neoplasm in men in the Western countries. It is well established that genetic and epigenetic alterations are common events in prostate cancer, which may lead to aberrant expression of critical genes. Most of the studies are focused on the overexpressed or duplicated genes in prostate cancer. However, it is known that some of the differentially expressed genes in prostate cancer are downregulated. Since the inventory of downregulated genes is incomplete, we performed in silico approaches to reveal the novel prostate cancer downregulated genes. Moreover, we also investigated for a possible link between the expression of the downregulated genes and tumor grade, recurrence, metastasis, or survival status in prostate cancer. Our results showed that the expression of GSTP1 and AOX1 are downregulated in prostate cancer, in concordance with previous reports. Moreover, we showed that TPM2, CLU, and COL4A6 mRNA levels are downregulated in prostate cancer. Further, we found a significant negative correlation between the expression of the above-mentioned genes and the prognosis of prostate cancer.