Altered microRNA (miRNA; miR) expression is associated with tumor formation and progression of various solid cancers. A major challenge in miRNA 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 miRNAs in a subpopulation of epithelial stem/progenitor-like cells in human prostate cancer [prostate cancer stem cell (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 (ALDH(high)) 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’-untranslated regions of proinvasive α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.