Children with advanced stages (relapsed/refractory and stage IV) of rhabdomyosarcoma (RMS) have a poor prognosis despite intensive chemotherapy and autologous stem cell rescue, with 5-year survival rates ranging from 5 to 35 %. Development of new, additional treatment modalities is necessary to improve the survival rate. In this preclinical study, we investigated the potential of resting and cytokine-activated natural killer (NK) cells to lyse RMS cell lines, as well as the pathways involved, to explore the eventual clinical application of (activated) NK cell immunotherapy. RMS cell lines (n = 3 derived from embryonal RMS and n = 2 derived from alveolar RMS) were susceptible to cytolysis mediated by resting NK cells, and this susceptibility was significantly increased using IL-15-activated NK cells. Flow cytometry and cytolytic assays were used to define the activating and inhibitory pathways of NK cells involved in recognizing and lysing RMS cells. NKG2D and DNAM-1 receptor-ligand interactions were essential in cytolysis by resting NK cells, as simultaneous blocking of both pathways resulted in almost complete abrogation of the cytotoxicity. In contrast, combined blocking of DNAM-1 and NKG2D only led to partial reduction of the lytic activity of IL-15-activated NK cells. In this respect, residual lysis was, at least partly, mediated by pathways involving the natural cytotoxicity receptors NKp30 and NKp46. These findings support further exploration of NK cell-based immunotherapy as adjuvant modality in current treatment strategies of RMS.