Current treatment regimens for rhabdomyosarcoma (RMS), the most common pediatric soft tissue cancer, rely on conventional chemotherapy, and although they show clinical benefit, there is a significant risk of adverse side effects and secondary tumors later in life. Therefore, identifying and targeting sub-populations with higher tumorigenic potential and self-renewing capacity would offer improved patient management strategies. Hedgehog signaling has been linked to the development of embryonal RMS (ERMS) through mouse genetics and rare human syndromes. However, activating mutations in this pathway in sporadic RMS are rare and therefore the contribution of hedgehog signaling to oncogenesis remains unclear. Here, we show by genetic loss-and gain-of-function experiments and the use of clinically relevant small molecule modulators that hedgehog signaling is important for controlling self-renewal of a subpopulation of RMS cells in vitro and tumor initiation in vivo. In addition, hedgehog activity altered chemoresistance, motility and differentiation status. The core stem cell gene NANOG was determined to be important for ERMS self-renewal, possibly acting downstream of hedgehog signaling. Crucially, evaluating the presence of a subpopulation of tumor-propagating cells in patient biopsies identified by GLI1 and NANOG expression had prognostic significance. Hence, this work identifies novel functional aspects of hedgehog signaling in ERMS, redefines the rationale for its targeting as means to control ERMS self-renewal and underscores the importance of studying functional tumor heterogeneity in pediatric cancers.