Altered microRNA (miR) expression is associated with tumor formation and progression of various solid cancers. A major challenge in miR expression profiling of bulk tumors is represented by the heterogeneity of the subpopulations of cells that constitute the organ, as well as the tumor tissue. Here we analyzed the expression of miRs in a subpopulation of epithelial stem/progenitor-like cells in human prostate cancer (PCSC) and compared their expression profile to more differentiated cancer cells. In both cell lines and clinical prostate cancer specimens we identified that miR-25 expression in PCSCs was low/absent and steadily increased during their differentiation into cells with a luminal epithelial phenotype. Functional studies revealed that overexpression of miR-25 in prostate cancer cell lines and selected subpopulation of highly metastatic and tumorigenic cells (ALDHhigh) strongly affected the invasive cytoskeleton causing reduced migration in vitro and metastasis via attenuation of extravasation in vivo. Here we show, for the first time, that miR-25 can act as a tumor suppressor in highly metastatic PCSCs by direct functional interaction with the 3'UTR of pro-invasive αv- and α6 integrins. Taken together, our observations suggest that miR-25 is a key regulator of invasiveness in human prostate cancer through its direct interactions with αv- and α6 integrin expression.