MicroRNAs (miRs) are a novel class of small RNA molecules, the dysregulation of which can contribute to cancer. A combinatorial approach was used to identify miRs that promote prostate cancer progression in a unique set of prostate cancer cell lines, which originate from the parental p69 cell line and extend to a highly tumorigenic/metastatic M12 subline. Together, these cell lines are thought to mimic prostate cancer progression in vivo. Previous network analysis and miR arrays suggested that the loss of hsa-miR-125b together with the overexpression of hsa-miR-22 could contribute to prostate tumorigenesis. The dysregulation of these two miRs was confirmed in human prostate tumor samples as compared to adjacent benign glandular epithelium collected through laser capture microdissection from radical prostatectomies. In fact, alterations in hsa-miR-125b expression appeared to be an early event in tumorigenesis. Reverse phase microarray proteomic analysis revealed ErbB2/3 and downstream members of the PI3K/AKT and MAPK/ERK pathways as well as PTEN to be protein targets differentially expressed in the M12 tumor cell compared to its parental p69 cell. Relevant luciferase+3'-UTR expression studies confirmed a direct interaction between hsa-miR-125b and ErbB2 and between hsa-miR-22 and PTEN. Restoration of hsa-miR-125b or inhibition of hsa-miR-22 expression via an antagomiR resulted in an alteration of M12 tumor cell behavior in vitro. Thus, the dual action of hsa-miR-125b as a tumor suppressor and hsa-miR-22 as an oncomiR contributed to prostate tumorigenesis by modulations in PI3K/AKT and MAPK/ERK signaling pathways, key pathways known to influence prostate cancer progression.