Inclusion Criteria:

* Patients must be =\< 50 years of age at the time of enrollment
* Patients with newly diagnosed RMS of any subtype, except adult-type pleomorphic, based upon institutional histopathologic classification are eligible to enroll on the study based upon stage, group, and age, as below. FOXO1 fusion status must be determined by week 4 (day 28) of therapy. RMS types included under embryonal RMS (ERMS) include those classified in the 1995 International Classification of Rhabdomyosarcoma (ICR) as ERMS (classic, spindle cell, and botryoid variants), which are reclassified in the 2020 World Health Organization (WHO) Classification as ERMS (classic, dense and botryoid variants) and spindle cell/sclerosing RMS (encompassing the historical spindle cell ERMS variant and the newly recognized sclerosing RMS variant). Classification of alveolar RMS (ARMS) in the 2020 WHO Classification is the same as in the ICR and includes classic and solid variants

* ERMS

* Stage 4, group IV, \>= 10 years of age
* ARMS

* Stage 4, group IV Patients will be eligible to remain on protocol therapy based upon stage, group, and age
* Bone marrow metastatic disease is based on morphologic evidence of RMS based on hematoxylin and eosin (H\&E) stains. In the absence of morphologic evidence of marrow involvement on H\&E, patients with bone marrow involvement detected ONLY by flow cytometry, reverse transcriptase (RT)-polymerase chain reaction (PCR), fluorescence in situ hybridization (FISH), or immunohistochemistry will NOT be considered to have clinical bone marrow involvement for the purposes of this study
* Creatinine clearance or radioisotope glomerular filtration rate (GFR) \>= 70 mL/min/1.73 m\^2 or a serum creatinine based on age/gender as follows (must be performed within 7 days prior to enrollment):

* Age; Maximum serum creatinine (mg/dL)
* 1 month to \< 6 months; 0.4 mg/dL (male); 0.4 mg/dL (female)
* 6 months to \< 1 year; 0.5 mg/dL (male); 0.5 mg/dL (female)
* 1 to \< 2 years; 0.6 mg/dL (male); 0.6 mg/dL (female)
* 2 to \< 6 years; 0.8 mg/dL (male); 0.8 mg/dL (female)
* 6 to \< 10 years; 1 mg/dL (male); 1 mg/dL (female)
* 10 to \< 13 years; 1.2 mg/dL (male); 1.2 mg/dL (female)
* 13 to \< 16 years; 1.5 mg/dL (male); 1.4 mg/dL (female)
* \>= 16 years; 1.7 mg/dL (male); 1.4 mg/dL (female)
* Total bilirubin =\< 1.5 x upper limit of normal (ULN) for age (must be performed within 7 days prior to enrollment)

* If there is evidence of biliary obstruction by tumor, then total bilirubin must be \< 3 x ULN for age
* All patients and/or their parents or legal guardians must sign a written informed consent
* All institutional, Food and Drug Administration (FDA), and National Cancer Institute (NCI) requirements for human studies must be met

Exclusion Criteria:

* Patients with evidence of uncontrolled infection are not eligible
* RMS that is considered a second malignancy and previous cancer(s) that were treated with chemotherapy and/or radiation. Surgical resection alone of previous cancer(s) is allowed
* Patients with central nervous system involvement of RMS as defined below:

* Malignant cells detected in cerebrospinal fluid
* Intra-parenchymal brain metastasis separate and distinct from primary tumor (i.e., direct extension from parameningeal primary tumors is allowed).
* Diffuse leptomeningeal disease
* Patients who have received any chemotherapy (excluding steroids) and/or radiation therapy for RMS prior to enrollment.

* Note: the following exception:

* Patients requiring emergency radiation therapy for RMS. These patients are eligible, provided they are consented to ARST2031 prior to administration of radiation
* Note: Patients who have received or are receiving chemotherapy or radiation for non-malignant conditions (e.g. autoimmune diseases) are eligible. Patients must discontinue chemotherapy for non-malignant conditions prior to starting protocol therapy
* Vincristine and vinorelbine are sensitive substrates of CYP450 3A4 isozyme. Patients must not have received drugs that are moderate to strong CYP3A4 inhibitors and inducers within 7 days prior to study enrollment
* Female patients who are pregnant since fetal toxicities and teratogenic effects have been noted for several of the study drugs. A pregnancy test is required for female patients of childbearing potential
* Lactating females who plan to breastfeed their infants
* Sexually active patients of reproductive potential who have not agreed to use an effective contraceptive method for the duration of their study participation