Rhabdomyosarcoma (RMS) is a pediatric soft tissue sarcoma arising from myogenic precursors that have lost their capability to differentiate into skeletal muscle. The polycomb-group protein EZH2 is a Lys27 histone H3 methyltransferase that regulates the balance between cell proliferation and differentiation by epigenetically silencing muscle-specific genes. EZH2 is often over-expressed in several human cancers acting as an oncogene. We previously reported that EZH2 inhibition induces cell cycle arrest followed by myogenic differentiation of RMS cells of the embryonal subtype (eRMS). MiR-101 is a microRNA involved in a negative feedback circuit with EZH2 in different normal and tumor tissues. To that, miR-101 can behave as a tumor suppressor in several cancers by repressing EZH2 expression. We, therefore, evaluated whether miR-101 is de-regulated in eRMS and investigated its interplaying with EZH2 as well as its role in the in vitro tumorigenic potential of these tumor cells. Herein, we report that miR-101 is down-regulated in eRMS patients and in tumor cell lines compared to their controls showing an inverse pattern of expression with EZH2. We also show that miR-101 is up-regulated in eRMS cells following both genetic and pharmacological inhibition of EZH2. In turn, miR-101 forced expression reduces EZH2 levels as well as restrains the migratory potential of eRMS cells and impairs their clonogenic and anchorage-independent growth capabilities. Finally, EZH2 recruitment to regulatory region of miR-101-2 gene decreases in EZH2-silenced eRMS cells. This phenomenon is associated to reduced H3K27me3 levels at the same regulatory locus, indicating that EZH2 directly targets miR-101 for repression in eRMS cells. Altogether, our data show that, in human eRMS, miR-101 is involved in a negative feedback loop with EZH2, whose targeting has been previously shown to halt eRMS tumorigenicity. They also demonstrate that the re-induction of miR-101 hampers the tumor features of eRMS cells. In this scenario, epigenetic dysregulations confirm their crucial role in the pathogenesis of this soft tissue sarcoma. The online version of this article (doi:10.1186/s13148-015-0107-z) contains supplementary material, which is available to authorized users