MicroRNAs (miRNAs) are short RNA nucleotides that negatively regulate their target genes. They are differentially expressed in prostate cancer. Kallikreins are genes that encode serine proteases and are dysregulated in cancer. We elucidated a miRNA-kallikrein network that can be involved in prostate cancer progression. Target prediction identified 23 miRNAs that are dysregulated between high and low risk biochemical failure and are predicted to target five kallikreins linked to prostate cancer; KLK2, KLK3, KLK4, KLK14 and KLK15. We also identified 14 miRNAs that are differentially expressed between Gleason grades and are predicted to target these kallikreins. This demonstrates that kallikreins are downstream effectors through which miRNAs influence tumor progression. We show, through in-silico and experimental analysis, that miR-378/422a and its gene targets PIK3CG, GRB2, AKT3, KLK4 and KLK14 form an integrated circuit in prostate cancer. Our analysis shows that a minisatellite sequence in the kallikrein locus consists of a number of microsatellite repeats that represent predicted miRNA response elements. A number of kallikrein and non-kallikrein prostate cancer-related genes share these microsatellite repeats. We validated some of these interactions in prostate cancer cell lines. Finally, we provide preliminary evidence on the presence of a miRNA-mediated cross-talk between kallikreins, including a kallikrein pseudogene.