• Histologically confirmed cutaneous or visceral angiosarcoma, where curative treatment is either not possible or curative modality therapy is declined by the subject. Note: If a subject declines curative modality therapy, the reason must be documented (e.g. excessive morbidity to necessary surgery)

‣ Note: Radiation induced angiosarcomas are permitted

• All local diagnostic slides AND 5 x 4-6 micron unstained slides from diagnostic tumor tissue should be available for retrospective central pathology review

• Must have measurable disease per Response Evaluation Criteria in Solid Tumors (RECIST) v1.1. Per RECIST v1.1, clinical lesions will only be considered measurable when they are superficial and \>= 10 mm diameter as assessed using calipers or ruler (e.g. skin nodules). For the case of skin lesions, documentation by color photography including a ruler to estimate the size of the lesion is required. When lesions can be evaluated by both clinical exam and imagining, imaging evaluation should be undertaken since it is more objective and may also be reviewed at the end of the study. The same method of measurement should be used throughout the study, preferably performed by the same investigator. Areas previously radiated must have demonstrated disease progression at some point over the past 6 months and growth must be subsequent to the last line of anti-cancer directed therapy (e.g. chemotherapy, radiation therapy, surgery)

• Not pregnant and not nursing, because this study involves an investigational agent whose genotoxic, mutagenic and teratogenic effects on the developing fetus and newborn are unknown

‣ Therefore, for women of childbearing potential only, a negative pregnancy test done =\< 3 days prior to registration is required

• Age \>= 18 years

• Eastern Cooperative Oncology Group (ECOG) performance status 0-1

• Prior Treatment

‣ Patient must have completed all prior cancer directed therapies (including investigational) \>= 7 days prior to cycle 1 day 1

• Exception: prostate patients who are allowed to concurrently receive androgen suppression therapy

∙ Note: Radiation therapy must be completed \>= 7 days of day 1 of study treatment, and must not be expected to significantly impact blood count recovery

⁃ There is no limit to overall number of prior lines of therapy

⁃ No prior PD-1 inhibitor or PD-L1 inhibitor therapy is permitted

⁃ No prior administration of VEGF TKI therapy is permitted

⁃ Recovery to baseline or' =\< grade 1 CTCAE version 5.0 from toxicity related to any prior treatment, unless adverse events are clinically non-significant and/or stable on supportive therapy, with the exception of fatigue (which should be =\< grade 2) or alopecia. Note: Patients should be expected to have experienced any nadir and have adequate blood count recovery prior to cycle 1 day 1

• Taxane Naive Patients Only: No prior exposure to taxane therapy of any duration for angiosarcoma

• Taxane Pre-treated Patients Only (Effective 10/28/2021, new patient accrual to Arm 3 was permanently closed): Prior taxane therapy is allowed at any point prior to registration as long as prior treatment eligibility criteria are met prior to cycle 1 day 1

• No major surgery (except the diagnostic biopsy) =\< 28 days of study registration. Procedures such as thoracentesis, paracentesis, percutaneous biopsy, Lasik eye surgery are not considered major surgery. Subjects with clinically relevant ongoing complications from prior surgery are not eligible

• Absolute neutrophil count (ANC) \>= 1,500/mm\^3

• Platelet count \>= 100,000/mm\^3

• Hemoglobin \>= 9.0 g/dL

• Calculated (Calc.) creatinine clearance \>= 30 mL/min (per Cockcroft-Gault)

• Total bilirubin =\< 1.5 x upper limit of normal (ULN)

‣ For patients with documented/suspected Gilbert's disease, bilirubin =\< 3 x ULN

• Aspartate aminotransferase (AST)/alanine aminotransferase (ALT) =\< 2.5 x upper limit of normal (ULN)

‣ For patients with significant hepatic metastases, ALT and AST =\< 5 x ULN. No clinically active or chronic liver disease resulting in moderate/severe hepatic impairment (Child-Pugh class B or C), ascites, coagulopathy or bleeding due to liver dysfunction

• Urine protein:creatinine (UPC) ratio \< 1 or urine protein =\< 1+ (Only for Arm 3 Taxane pre-treated and crossover patients)

• No uncontrolled central nervous system (CNS) metastases. Patients with history of CNS metastasis will be allowed as long as the metastatic sites were adequately treated as demonstrated by clinical and radiographic improvement, and the patient has recovered from the intervention (no residual adverse events \> CTCAE grade 1), and the patient has remained without recurrence of new or worsening CNS symptoms for a period of 28 days prior to registration. Treated CNS metastasis (mets) should have no ongoing requirement for steroids, and no evidence of hemorrhage after treatment for at least 28 days prior to registration

• No uncontrolled intercurrent illness that would put the patient at undue risk by participation in the study, in the opinion of the investigator

• No history of syncope of cardiovascular etiology, uncontrolled cardiac arrhythmia, history of Mobitz II second degree or third degree heart block without a permanent pacemaker in place, myocardial ischemia or infarction, severe or unstable angina, New York Heart Association (NYHA) class II to IV heart failure, or stroke/transient ischemic attack (TIA) within the past 3 months

• No thromboembolic event (e.g., deep venous thrombosis, pulmonary embolism) within 1 month before randomization. Subjects with a diagnosis of incidental, subsegmental pulmonary embolism (PE) or deep vein thrombosis (DVT) within 6 months are allowed if stable, asymptomatic, and treated with low molecular weight heparin (LMWH) for at least 2 weeks before first dose. Iatrogenic arterial embolization procedures such as tumor arterial embolization or splenic artery embolization are allowed

• Patients with a requirement for steroid treatment or other immunosuppressive treatment: Patients should be excluded if they have a condition requiring systemic treatment with either corticosteroids (\> 10 mg daily prednisone equivalents) or other immunosuppressive medications within 14 days of study drug administration. Inhaled or topical steroids and adrenal replacement doses \> 10 mg daily prednisone equivalents are permitted in the absence of active autoimmune disease. Patients are permitted to use topical, ocular, intra-articular, intranasal, and inhalational corticosteroids (with minimal systemic absorption). A brief course of corticosteroids for prophylaxis (e.g., contrast dye allergy) or for treatment of non-autoimmune conditions (e.g., delayed-type hypersensitivity reaction caused by contact allergen) is permitted

• Patients are permitted to enroll if they have vitiligo, type I diabetes mellitus, residual hypothyroidism due to autoimmune condition only requiring hormone replacement, psoriasis not requiring systemic treatment, or conditions not expected to recur in the absence of an external trigger (precipitating event)

• Active autoimmune disease requiring systemic treatment (i.e. disease modifying agents, corticosteroids, or immunosuppressive drugs) within the past 2 years. These include but are not limited to patients with a history of immune-related neurologic disease, multiple sclerosis, autoimmune (demyelinating) neuropathy, Guillain-Barre syndrome, myasthenia gravis; systemic autoimmune disease such as systemic lupus erythematosus (SLE), rheumatoid arthritis, connective tissue diseases, scleroderma, inflammatory bowel disease (IBD), Crohn's, ulcerative colitis, hepatitis; and patients with a history of toxic epidermal necrolysis (TEN), Stevens-Johnson syndrome, or phospholipid syndrome should be excluded because of the risk of recurrence or exacerbation of disease

‣ Note: Patients are permitted to enroll if they have vitiligo; type I diabetes mellitus; hypothyroidism, pituitary or adrenal insufficiency requiring only hormone replacement; psoriasis not requiring systemic treatment, or conditions not expected to recur in the absence of an external trigger (precipitating event)

• Human immunodeficiency virus (HIV)-infected patients on effective anti-retroviral therapy with undetectable viral load within 6 months are eligible for this trial

• No planned palliative procedures for alleviation of pain such as radiation therapy or surgery

• No untreated or impending spinal cord compression or evidence of spinal metastases with a risk of impending fracture or spinal cord compression

• No known or suspected contraindications or hypersensitivity to paclitaxel, cabozantinib or nivolumab or to any of the excipients

• Disorders associated with a high risk of perforation or fistula formation: active inflammatory bowel disease, active diverticulitis, active cholecystitis, active symptomatic cholangitis or active appendicitis, active acute pancreatitis or active acute obstruction of the pancreatic or biliary duct, or active gastric outlet obstruction; abdominal fistula, gastrointestinal perforation, bowel obstruction, or intra-abdominal abscess within 6 months before randomization. Note: Complete healing of an intra-abdominal abscess must be confirmed before randomization

• No clinically significant hematuria, hematemesis, or hemoptysis, or other history of significant bleeding (e.g., pulmonary hemorrhage) within 3 months before randomization

• No lesions invading major pulmonary blood vessels

• No other clinically significant disorders: uncompensated/symptomatic hypothyroidism; requirements for hemodialysis or peritoneal dialysis; history of solid organ transplantation

• Serious non-healing wounds unrelated to cancer are excluded

‣ Note: Wounds that are cutaneous angiosarcoma are allowed

• Chronic concomitant treatment with strong inhibitors and inducers of CYP3A4 is not allowed on this study. Patients on strong CYP3A4 inhibitors and inducers must discontinue the drug 7 days and 14 days, respectively prior to registration on the study

• Taxane Naive Patients Only: No clinically significant neuropathy (grade \>= 2 per NCI CTCAE v5.0)

• Taxane Pre-treated only (Effective 10/28/2021, new patient accrual to Arm 3 was permanently closed):

‣ Stroke (including transient ischemic attack \[TIA\]), myocardial infarction (MI), or other ischemic event, or thromboembolic event (e.g., deep venous thrombosis, pulmonary embolism) within 6 months before first dose. Subjects with a diagnosis of DVT within 6 months are allowed if stable and treated with LMWH for at least 2 weeks before first dose

⁃ No history of clinically significant coagulopathy

⁃ No uncontrolled hypertension, defined as systolic blood pressure of \> 140 mmHg or diastolic pressure \> 90 mmHg on anti-hypertensive medications

⁃ No known or suspected gastrointestinal disorder affecting absorption of oral medications (for patients getting cabozantinib)

• No clinical, laboratory or radiographic evidence of an active bacterial, fungal, or viral infection requiring treatment at the time of registration. No concurrent use of parenteral (IV) antibiotics is permitted. Oral antibiotics administered for a defined course with expectation of resolution of infection are permitted at the discretion of the investigator

• No use of ongoing systemic steroid therapy within 7 days prior to study registration. Dose equivalence of prednisone 10mg daily or less is permitted

• Taxane Pre-treated only:

‣ No current use of aspirin (\> 81 mg/day), or any other antiplatelet agents

⁃ Concomitant anticoagulation with oral anticoagulants (e.g., warfarin, direct thrombin inhibitors, and factor Xa inhibitors) or platelet inhibitors (e.g., clopidogrel) is not permitted. Low-dose (prophylactic) low molecular weight heparins (LMWH) are permitted. Anticoagulation with therapeutic doses of LMWH is allowed in subjects with no known brain metastases, no clinically significant hemorrhage, or no complications from a thromboembolic event on the anticoagulation regimen, and who have been on a stable dose of LMWH for at least 2 weeks before first dose

• Patients must be able to speak and comprehend English or Spanish in order to complete the mandatory patient-completed measures

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): Not pregnant and not nursing, because this study involves an investigational agent whose genotoxic, mutagenic and teratogenic effects on the developing fetus and newborn are unknown

‣ Therefore, for women of childbearing potential only, a negative pregnancy test done =\< 3 days prior to re-registration is required

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): Age \>= 18 years

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): ECOG performance status 0-1

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): Prior Treatment

‣ Patient must have completed all prior treatments (including investigational Arm 2 paclitaxel) \>= 28 days prior to cycle 1 day 1

• Exception: prostate patients who are allowed to concurrently receive androgen suppression therapy

∙ Note: Re-registration is only permitted after progression on Arm 2

⁃ No prior PD-1 inhibitor or PD-L1 inhibitor therapy is permitted

⁃ Recovery to baseline, or =\< grade 1 CTCAE version 5.0 from toxicity related to any prior treatment, unless adverse events are clinically non-significant and/or stable on supportive therapy, with the exception of fatigue (which should be =\< grade 2) or alopecia. Note: Patients should be expected to have experienced any nadir and have adequate blood count recovery prior to cycle 1 day 1

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): No major surgery (except the diagnostic biopsy) =\< 28 days of study re-registration. Procedures such as thoracentesis, paracentesis, percutaneous biopsy, Lasik eye surgery are not considered major surgery. Subjects with clinically relevant ongoing complications from prior surgery are not eligible

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): Absolute neutrophil count (ANC) \>= 1,500/mm\^3

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): Platelet count \>= 100,000/mm\^3

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): Hemoglobin \>= 9.0 g/dL

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): Calc. creatinine clearance \>= 30 mL/min (per Cockcroft-Gault)

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): Total bilirubin =\< 1.5 x upper limit of normal (ULN)

‣ For patients with documented/suspected Gilbert's disease, bilirubin =\< 3 x ULN

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): AST/ALT =\< 2.5 x upper limit of normal (ULN)

‣ For patients with significant hepatic metastases, ALT and AST =\< 5 x ULN. No clinically active or chronic liver disease resulting in moderate/severe hepatic impairment (Child-Pugh class B or C), ascites, coagulopathy or bleeding due to liver dysfunction

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): UPC ratio \< 1 or urine protein =\< 1+

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): No uncontrolled CNS metastases. Patients with history of CNS metastasis will be allowed as long as the metastatic sites were adequately treated as demonstrated by clinical and radiographic improvement, and the patient has recovered from the intervention (no residual adverse events \> CTCAE grade 1), and the patient has remained without recurrence of new or worsening CNS symptoms for a period of 28 days prior to registration. Treated CNS mets should have no ongoing requirement for steroids, and no evidence of hemorrhage after treatment for at least 28 days prior to registration

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): No uncontrolled intercurrent illness that would put the patient at undue risk by participation in the study, in the opinion of the investigator

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): No history of syncope of cardiovascular etiology, uncontrolled cardiac arrhythmia, History of Mobitz II second degree or third degree heart block without a permanent pacemaker in place, myocardial ischemia or infarction, severe or unstable angina, New York Heart Association (NYHA) class II to IV heart failure, or stroke/transient ischemic attack (TIA) within the past 3 months

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): No thromboembolic event (e.g., deep venous thrombosis, pulmonary embolism) within 1 month before randomization. Subjects with a diagnosis of incidental, subsegmental PE or DVT within 6 months are allowed if stable, asymptomatic, and treated with LMWH for at least 2 weeks before first dose. Iatrogenic arterial embolization procedures such as tumor arterial embolization or splenic artery embolization are allowed

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): Patients with a requirement for steroid treatment or other immunosuppressive treatment: Patients should be excluded if they have a condition requiring systemic treatment with either corticosteroids (\> 10 mg daily prednisone equivalents) or other immunosuppressive medications within 14 days of study drug administration. Inhaled or topical steroids and adrenal replacement doses \> 10 mg daily prednisone equivalents are permitted in the absence of active autoimmune disease. Patients are permitted to use topical, ocular, intra-articular, intranasal, and inhalational corticosteroids (with minimal systemic absorption). A brief course of corticosteroids for prophylaxis (e.g., contrast dye allergy) or for treatment of non-autoimmune conditions (e.g., delayed-type hypersensitivity reaction caused by contact allergen) is permitted

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): Active autoimmune disease requiring systemic treatment (i.e. disease modifying agents, corticosteroids, or immunosuppressive drugs) within the past 2 years. These include but are not limited to patients with a history of immune-related neurologic disease, multiple sclerosis, autoimmune (demyelinating) neuropathy, Guillain-Barre syndrome, myasthenia gravis; systemic autoimmune disease such as SLE, rheumatoid arthritis, connective tissue diseases, scleroderma, inflammatory bowel disease (IBD), Crohn's, ulcerative colitis, hepatitis; and patients with a history of toxic epidermal necrolysis (TEN), Stevens-Johnson syndrome, or phospholipid syndrome should be excluded because of the risk of recurrence or exacerbation of disease

‣ Note: Patients are permitted to enroll if they have vitiligo; type I diabetes mellitus; hypothyroidism, pituitary or adrenal insufficiency requiring only hormone replacement; psoriasis not requiring systemic treatment, or conditions not expected to recur in the absence of an external trigger (precipitating event)

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): HIV-infected patients on effective anti-retroviral therapy with undetectable viral load within 6 months are eligible for this trial

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): No planned palliative procedures for alleviation of pain such as radiation therapy or surgery

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): No untreated or impending spinal cord compression or evidence of spinal metastases with a risk of impending fracture or spinal cord compression

• Re-Registration Eligibility Criteria (upon progression on Arm 2 only): No known or suspected contraindications or hypersensitivity to cabozantinib or nivolumab or to any of the exc