Inclusion Criteria:

* Diagnosis

* Patients with first relapse or progression of rhabdomyosarcoma are eligible
* Patients with primary refractory disease are eligible

* Primary refractory disease is defined as first progression after receiving at least one course of cyclophosphamide or ifosfamide containing chemotherapy without prior demonstration of a radiographic response to chemotherapy (progression on irinotecan-containing chemotherapy without cyclophosphamide or ifosfamide containing chemotherapy will not be considered a first progression)
* Note: Patients without measurable or evaluable disease are eligible
* Patients must have had a previous histological verification of rhabdomyosarcoma at original diagnosis
* Patients must have a Karnofsky or Lansky performance status score of \>= 50%, corresponding to Eastern Cooperative Oncology Group (ECOG) categories of 0, 1, or 2; use Karnofsky for patients \> 16 years of age and Lansky for patients =\< 16 years of age
* Patients must have a life expectancy of \>= 8 weeks
* Patients must have fully recovered from the acute toxic effects of all prior chemotherapy, immunotherapy, or radiotherapy prior to entering this study
* Myelosuppressive chemotherapy: Must not have received within 3 weeks prior to entry onto this study (4 weeks if prior nitrosourea)
* Biologic (anti-neoplastic agent):

* Patients may have received prior therapy with oral tyrosine kinase inhibitors or other similar agents; at least 7 days must have elapsed since the completion of therapy with a biologic agent and all toxicities must have resolved to \< grade 2 prior to enrollment
* 3 half-lives (or 6 weeks) must have elapsed since previous monoclonal antibody therapy prior to enrollment on this study
* Myeloid growth factor: Must not have received within 1 week prior to entry onto this study
* Radiation therapy (RT): At least 4 weeks must have elapsed between RT and study entry; previously radiated lesions cannot be used to assess response unless those sites are the sites of disease progression
* Stem cell transplant (SCT): For autologous SCT, \>= 3 months must have elapsed; for allogeneic SCT, \>= 6 months must have elapsed and no evidence of active graft vs. host disease
* Patients must have recovered from any surgical procedure before enrolling on this study

* Minor surgical procedures (e.g., biopsies involving core or fine-needle aspiration procedures, infusaport or Broviac line placement, paracentesis, or thoracocentesis) need to have fully healed and occurred \> 7 days prior to enrollment
* Patients who have had a major surgical procedure (such as laparotomy, thoracotomy, open biopsy, or resection of tumor) can only be enrolled on study \> 28 days from such procedure
* Peripheral absolute neutrophil count (ANC) \>= 750/μL
* Platelet count \>= 75,000/μL (transfusion independent, defined as without transfusion for \>= 1 week prior to enrollment)
* Hemoglobin \>= 8.0 g/dL (may receive packed red blood cells \[PRBC\] transfusions)
* Bone marrow disease involvement of tumor is allowed, however, peripheral blood count criteria must still be met
* 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:

* =\< 0.4 mg/dL (for patients aged 1 month to \< 6 months)
* =\< 0.5 mg/dL (for patients aged 6 months to \< 1 year)
* =\< 0.6 mg/dL (for patients aged 1 to \< 2 years)
* =\< 0.8 mg/dL (for patients aged 2 to \< 6 years)
* =\< 1 mg/dL (for patients aged 6 to \< 10 years)
* =\< 1.2 mg/dL (for patients aged 10 to \< 13 years)
* =\< 1.4 mg/dL (for female patients aged \>= 13 years)
* =\< 1.5 mg/dL (for male patients aged 13 to \< 16 years)
* =\< 1.7 mg/dL (for male patients aged \>= 16 years)
* Urine protein level:

* Patients aged =\< 17 years: Urine protein to creatinine (UPC) ratio should be calculated; UPC ratio must be =\< 1 for patient to be eligible
* Patients aged \> 17 years: Urine protein should be screened by urine analysis; if protein is 2+ or higher, 24-hour urine protein must be obtained and the level must be \< 1,000 mg for patient enrollment
* Total bilirubin =\< 1.5 x upper limit of normal (ULN) for age
* Shortening fraction of \>= 27% by echocardiogram or ejection fraction of \>= 50% by radionuclide angiogram

Exclusion Criteria:

* Patients with botryoid histology, any stage or group, are ineligible
* Patients with embryonal histology, stage I or clinical group 1 at initial disease presentation, who present with local or regional recurrence, are ineligible
* Patients who previously received craniospinal irradiation are ineligible
* Patients who previously received vinorelbine, bevacizumab, temsirolimus, or any other direct vascular endothelial growth factor (VEGF)/vascular endothelial growth factor receptor (VEGFR-) or mammalian target of rapamycin (mTOR-) targeting agents are ineligible
* Patients with known central nervous system (CNS) disease (excluding intracranial/intraspinal extension secondary to local progression of a parameningeal or paraspinal primary), except for those with treated brain metastasis, are ineligible

* Treated brain metastases are defined as having no ongoing requirement for steroids and no evidence of progression or hemorrhage after treatment for at least 3 months, as ascertained by clinical examination and brain imaging (magnetic resonance imaging \[MRI\] or computed tomography \[CT\]); stable dose of anticonvulsants are allowed; treatment for brain metastases may include whole-brain radiotherapy (WBRT), radiosurgery (RS; Gamma Knife, linear accelerator \[LINAC\], or equivalent), or a combination as deemed appropriate by the treating physician
* Patients with CNS metastases treated within 3 months prior to enrollment by neurosurgical resection or brain biopsy are ineligible
* Patients who receive radiation or chemotherapy (inclusive of palliative intent) for first disease progression or relapse of rhabdomyosarcoma prior to enrollment are ineligible
* Female patients who are pregnant are ineligible
* Lactating females are not eligible unless they have agreed to discontinue breastfeeding
* Female patients of childbearing potential are not eligible unless a negative pregnancy test result has been obtained
* Sexually active patients of reproductive potential are not eligible unless they have agreed to use an effective contraceptive method for the duration of their study participation
* Patients with a documented chronic non-healing wound, ulcer, or significant trauma injury (those with bone fractures, including pathological fractures, or requiring surgical intervention) within 28 days prior to beginning therapy are ineligible
* Patients with evidence of intratumoral hemorrhage, gastrointestinal bleeding, or on anticoagulation for thrombosis or history of thrombosis are ineligible
* Patients with uncontrolled hypertension are ineligible; uncontrolled hypertension is defined as follows:

* Patients aged =\< 17 years: greater than 95th percentile systolic and diastolic blood pressure based on age and height that is not controlled by one antihypertensive medication
* Patients aged \> 17 years: systolic blood pressure \>= 160 mm Hg and/or diastolic blood pressure \>= 90 mm Hg that is not controlled by one antihypertensive medication
* Patients currently taking anticoagulants or antiplatelet agents with the exception of aspirin (=\< 81 mg/day) are ineligible
* Patients with history of central venous catheter (CVC)-associated thrombosis requiring systemic anticoagulation are ineligible; Note: Patients with history of sluggish flow from CVC or CVC-associated thrombosis treated with tissue plasminogen activator (TPA) only are not excluded
* Patients with clinically significant cardiovascular disease are excluded:

* History of cerebrovascular accident (CVA) within the prior 6 months
* Myocardial infarction or unstable angina within the prior 6 months
* New York Heart Association grade 2 or greater congestive heart failure
* Serious and inadequately controlled cardiac arrhythmia
* Significant vascular disease (e.g., aortic aneurysm, history of aortic dissection)
* Clinically significant peripheral vascular disease
* Patients diagnosed with rhabdomyosarcoma as a second malignant neoplasm are not eligible
* Patients with history of any second malignant neoplasm who have received chemotherapy or radiation for the treatment of that malignancy are not eligible