Kaiso, a member of the BTB/POZ zinc finger protein family, functions as a transcriptional repressor by binding to sequence-specific Kaiso binding sites or to methyl-CpG dinucleotides. Previously, we demonstrated that Kaiso overexpression and nuclear localization correlated with the progression of prostate cancer (PCa). Therefore, our objective was to explore the molecular mechanisms underlying Kaiso-mediated PCa progression. Comparative analysis of miRNA arrays revealed that 13 miRNAs were significantly altered (> 1.5 fold, p < 0.05) in sh-Kaiso PC-3 compared to sh-Scr control cells. Real-time PCR validated that three miRNAs (9, 31, 636) were increased in sh-Kaiso cells similar to cells treated with 5-aza-2'-deoxycytidine. miR-31 expression negatively correlated with Kaiso expression and with methylation of the miR-31 promoter in a panel of PCa cell lines. ChIP assays revealed that Kaiso binds directly to the miR-31 promoter in a methylation-dependent manner. Over-expression of miR-31 decreased cell proliferation, migration and invasiveness of PC-3 cells, whereas cells transfected with anti-miR-31 restored proliferation, migration and invasiveness of sh-Kaiso PC-3 cells. In PCa patients, Kaiso high/miR-31 low expression correlated with worse overall survival relative to each marker individually. In conclusion, these results demonstrate that Kaiso promotes cell migration and invasiveness through regulation of miR-31 expression.