microRNAs (miRNAs) are short non-coding RNAs, which regulate gene expression post-transcriptionally and play crucial roles in relevant biological and pathological processes. Here we investigated the putative role of miRNAs in modulating the tumor-initiating potential of mouse medulloblastoma (MB)-derived cancer stem cells (CSCs). We first subjected bona fide highly tumorigenic (HT) CSCs as well as lowly tumorigenic (LT) MB CSCs and normal neural stem cells (NSCs) to miRNA profiling, which identified a HT CSC-specific miRNA signature. Next, by cross-checking CSC mRNA/miRNA profiles, we pinpointed miR-135a as a potential tumor suppressor gene, which was strongly downregulated in HT CSCs as well as in the highly malignant experimental tumors derived from them. Remarkably, enforced expression of miR-135a in HT CSCs strongly inhibited tumorigenesis by repressing the miR-135a direct target gene Arhgef6. Considering the upregulation of Arhgef6 in human MBs and its involvement in mediating experimental medulloblastomagenesis, its efficient suppression by miR-135a might make available an effective therapeutic strategy to selectively impair the tumorigenic potential of MB CSCs.