Prostate cancer is the most common cancer in men, and most patients have localized disease at the time of diagnosis. However, 4% already present with metastatic disease. Epithelial-mesenchymal transition is a fundamental process in carcinogenesis that has been shown to be involved in prostate cancer progression. The main event in epithelial-mesenchymal transition is the repression of E-cadherin by transcription factors, but the process is also regulated by microRNAs. The aim of this study was to analyze gene and microRNA expression involved in epithelial-mesenchymal transition in localized prostate cancer and metastatic prostate cancer cell lines and correlate with clinicopathological findings. We studied 51 fresh frozen tissue samples from patients with localized prostate cancer (PCa) treated by radical prostatectomy and three metastatic prostate cancer cell lines (LNCaP, DU145, PC3). The expression of 10 genes and 18 miRNAs were assessed by real-time PCR. The patients were divided into groups according to Gleason score, pathological stage, preoperative PSA, biochemical recurrence, and risk group for correlation with clinicopathological findings. The majority of localized PCa cases showed an epithelial phenotype, with overexpression of E-cadherin and underexpression of the mesenchymal markers. MiRNA-200 family members and miRNAs 203, 205, 183, 373, and 21 were overexpressed, while miRNAs 9, 495, 29b, and 1 were underexpressed. Low-expression levels of miRNAs 200b, 30a, and 1 were significantly associated with pathological stage. Lower expression of miR-200b was also associated with a Gleason score ≥ 8 and shorter biochemical recurrence-free survival. Furthermore, low-expression levels of miR-30a and high-expression levels of Vimentin and Twist1 were observed in the high-risk group. Compared with the primary tumor, the metastatic cell lines showed significantly higher expression levels of miR-183 and Twist1. In summary, miRNAs 200b, 30a, 1, and 183 and the genes Twist1 and Vimentin might play important roles in the progression of prostate cancer and may eventually become important prognostic markers.