Inclusion Criteria:
* Subjects must have a histologically confirmed diagnosis of unresectable or metastatic:
* Uterine and non-uterine leiomyosarcoma
* Other soft tissue sarcoma (non-leiomyosarcoma)
* Note: Subjects with any one of the following soft tissue sarcoma histological subtypes will not be eligible for participation: alveolar soft-part sarcoma, dermatofibrosarcoma, gastrointestinal stromal tumor (GIST), Kaposi sarcoma, mixed mesodermal tumor/carcinosarcoma, rhabdomyosarcoma (embryonal and alveolar), and low grade (grade 1) sarcomas
* Subjects must exhibit an Eastern Cooperative Oncology Group (ECOG) performance status of 0-1
* Subjects with 0 - 5 prior chemotherapy regimens for recurrent/metastatic disease are eligible. It will be up to the investigator to determine what constitutes a regimen in each case
* Subjects with prior next generation sequencing (NGS) reports completed on their tumor specimen will have this data collected
* Subjects must have measurable disease by RECIST 1.1
* Subjects must have adequate organ and bone marrow function, based upon meeting all of the following laboratory:
* White blood cell count \>= 2500/mm\^3 (\>= 2.5 GI/L)
* Absolute neutrophil count (ANC) \>= 1,500/mm\^3 (\>= 1.5 GI/L) without granulocyte colony stimulating factor support
* Hemoglobin \>= 9 g/dL (\>= 90 g/L)
* Platelets \>= 100,000/mm\^3 (\>= 100 GI/L) without transfusion
* Total bilirubin =\< 1.5 x upper limit of normal (ULN) (for subjects with Gilbert's disease =\< 3 x ULN)
* Aspartate aminotransferase (AST) (serum glutamic-oxaloacetic transaminase \[SGOT\])/alanine aminotransferase (ALT) (serum glutamate pyruvate transaminase \[SPGT\]) =\< 3 X upper limit of normal (ULN)
* Alkaline phosphatase (ALP) =\< 3 X ULN. ALP =\< 5 x ULN with documented bone metastases
* Serum albumin \>= 2.8 g/dl
* Serum creatinine =\< 2.0 x ULN or calculated creatinine clearance \>= 30 mL/min (\>= 0.5 mL/sec) using the Cockcroft-Gault equation
* Urine protein/creatinine ratio (UPCR) =\< 1 (=\< 113.2 mg/mmol)
* Prothrombin time (PT/institutional normalized ratio \[INR\]) or partial thromboplastin time (PTT) test =\< 1.3 x the laboratory ULN
* Sexually active fertile subjects and their partners must agree to use medically accepted methods of contraception (e.g., barrier methods, including male condom, female condom, or diaphragm with spermicidal gel) during the course of the study and for 4 months after the last dose of study treatment
* Female subjects of childbearing potential must not be pregnant at screening. Females of childbearing potential are defined as premenopausal females capable of becoming pregnant (i.e., females who have had any evidence of menses in the past 12 months, with the exception of those who had prior hysterectomy). However, women who have been amenorrheic for 12 or more months are still considered to be of childbearing potential if the amenorrhea is possibly due to prior chemotherapy, antiestrogens, low body weight, ovarian suppression or other reasons
* Recovery to baseline or =\< grade 1 Common Terminology Criteria for Adverse Events (CTCAE) version (v.)5.0 from toxicities related to any prior treatments, unless AE(s) are clinically nonsignificant and/or stable on supportive therapy
* Subjects with treated brain metastases are eligible if follow-up brain imaging after central nervous system (CNS)-directed therapy shows no evidence of progression
* Subjects must be capable of understanding and complying with the protocol requirements and must have signed the informed consent document
Exclusion Criteria:
* Inability to swallow tablets
* Previously identified allergy or hypersensitivity to components of the study treatment formulation or dacarbazine
* Subjects with a prior or concurrent malignancy whose natural history or treatment does have the potential to interfere with the safety or efficacy assessment of the investigational regiment are ineligible for this trial
* Pregnant or lactating females. Pregnant women are excluded from this study because cabozantinib and temozolomide are antineoplastic agents with potential for teratogenic or abortifacient effects. Because there is an unknown but potential risk for adverse events in nursing infants secondary to treatment of the mother with cabozantinib and temozolomide, breastfeeding should be discontinued if the mother is treated with cabozantinib and temozolomide
* Prior treatment with cabozantinib or temozolomide
* Receipt of any of the following:
* Any type of small molecule kinase inhibitor (including investigational kinase inhibitor) within 14 days before first dose of study treatment
* Any type of cytotoxic, biologic or other systemic anticancer therapy (including investigational) within 28 days before first dose of study treatment
* Radiation therapy for bone metastasis within 14 days before first dose of study treatment
* Any other radiation therapy within 28 days before first dose of study treatment
* Systemic treatment with radionuclides within 42 days before the first dose of study treatment
* Note: Subjects with clinically relevant ongoing complications from prior radiation therapy are not eligible
* Major surgery (e.g., GI surgery, removal or biopsy of brain metastasis) within 56 days before the first dose of study treatment
* Note: Complete wound healing from major surgery must have occurred 28 days before first dose and from minor surgery (e.g., simple excision, tooth extraction) at least 10 days before first dose. Subjects with clinically relevant ongoing complications from prior surgery are not eligible
* Corrected QT interval calculated by the Bazetts formula (QTcF) \> 500 ms per electrocardiogram (ECG) within 28 days before first dose of study treatment
* Note: If a single electrocardiography (ECG) shows a QTcF with an absolute value \> 500 ms, two additional ECGs at intervals of approximately 3 min must be performed within 30 min after the initial ECG, and the average of these three consecutive results for QTcF will be used to determine eligibility
* The subject has uncontrolled, significant intercurrent or recent illness including, but not limited to, the following conditions:
* Cardiovascular disorders:
* Subjects with known history or current symptoms of cardiac disease, or history of treatment with cardiotoxic agents, should have a clinical risk assessment of cardiac function using the New York Heart Association Functional Classification. To be eligible for this trial, subjects should be class 2B or better
* Uncontrolled hypertension defined as sustained blood pressure (BP) ˃ 150 mm Hg systolic or ˃ 100 mm Hg diastolic despite optimal antihypertensive treatment
* Stroke (including transient ischemic attack \[TIA\]), myocardial infarction (MI), or other ischemic event within 6 months before the first dose
* Gastrointestinal (GI) disorders including those associated with a high risk of perforation or fistula formation:
* The subject has evidence of tumor invading the GI tract, active peptic ulcer disease, inflammatory bowel disease (e.g., Crohn's disease), diverticulitis, cholecystitis, symptomatic cholangitis or appendicitis, acute pancreatitis, acute obstruction of the pancreatic duct or common bile duct, or gastric outlet obstruction.
* Abdominal fistula, GI perforation, bowel obstruction, or intra-abdominal abscess within 6 months before the first dose
* Note: Complete healing of an intra-abdominal abscess must be confirmed before the first dose
* Clinically significant hematuria, hematemesis, or hemoptysis of \> 0.5 teaspoon (2.5 ml) of red blood, or other history of significant bleeding (e.g., pulmonary hemorrhage) within 84 days before the first dose
* Cavitating pulmonary lesion(s) or known endotracheal or endobronchial disease manifestation
* Lesions invading or encasing any major blood vessels
* Other clinically significant disorders that would preclude safe study participation
* Serious non-healing wound/ulcer/bone fracture
* Uncompensated/symptomatic hypothyroidism
* Moderate to severe hepatic impairment (Child-Pugh B or C)
* Concomitant anticoagulation with oral anticoagulants (e.g., warfarin, direct thrombin and factor Xa inhibitors) or platelet inhibitors (e.g., clopidogrel). Washout period is considered to be 5 half-lives of the drug. Allowed anticoagulants are the following:
* Low-dose aspirin for cardio protection (per local applicable guidelines) is permitted.
* Low-dose low molecular weight heparins (LMWH) are permitted.
* Anticoagulation with therapeutic doses of LMWH is allowed in subjects without known brain metastases who are on a stable dose of LMWH for at least 42 days before first dose of study treatment, and who have had no clinically significant hemorrhagic complications from the anticoagulation regimen or the tumor
