Prostate cancer (PCa) is one of the most common types of cancer among men. To date, there have been no specific markers identified for the diagnosis and prognosis or response to treatment of this disease. Thus, there is an urgent need for promising markers, which may be fulfilled by small non-coding RNAs known as microRNAs (miRNAs). Therefore, the present study aimed to investigate the miRNA profile in tissue samples obtained from patients with PCa using microarrays, followed by reverse transcriptase quantitative PCRs (RT-qPCRs). In the discovery phase, 754 miRNAs were screened in tissues obtained from patients ( = 46) with PCa in early and late stages. Expression levels of miRNA-324-3p, miRNA-429, miRNA-570, and miRNA-616 were found to be downregulated, and miRNA-423-5p expression was upregulated in patients with early-stage cancer compared to the late-stage ones. These five miRNAs were further validated in an independent cohort of samples ( = 39) collected from patients with PCa using RT-qPCR-based assays. MiRNA-324-3p, miRNA-429, miRNA-570, and miRNA-616 expression levels remained significantly downregulated in early-stage cancer tissues compared to late-stage tissues. Remarkably, for a combination of three miRNAs, PSA levels and Gleason scores were able to discriminate between patients with early-stage PCa and late-stage PCa, with an AUC of 95%, a sensitivity of 86%, and a specificity close to 94%. Thus, the data obtained in this study suggest a possible involvement of the identified miRNAs in the pathogenesis of PCa, and they may also have the potential to be developed into diagnostic and prognostic tools for PCa. However, further studies with a larger cohort are needed.