Inclusion Criteria:

          -  Unresectable or metastatic melanoma of cutaneous, mucosal, conjunctival, or unknown
             origin. Uveal melanoma is not permitted. Cohort 1: Naïve to anti-PD1 therapy Cohort 2:
             Progressed on previous anti-PD1 therapy. Subjects who have received anti-PD1 therapy
             in the adjuvant setting for previously resected melanoma are eligible for this cohort
             provided they have not received any intervening systemic therapy for the relapse

          -  Be willing and able to provide written informed consent for the trial.

          -  Have measurable disease based on Response Evaluation Criteria in Solid Tumors (RECIST)
             version 1.1

          -  Females of childbearing potential should have a negative urine or serum pregnancy test
             within 72 hours prior to receiving the first dose of study medication.

          -  Females of childbearing potential should be willing to use 2 methods of birth control
             or be surgically sterile, or abstain from heterosexual activity for the course of the
             study 28 days after last dose of avadomide or 5 months after the last dose of
             nivolumab, whichever is longer. Females of childbearing potential are those who have
             not been surgically sterilized or have not been free from menses for >1 year.

          -  Males should agree to use an adequate method of contraception starting with the first
             dose of study therapy through 3 months after the last dose of avadomide or 7 months
             after last dose of nivolumab, whichever is longer.

          -  Adequate organ function

        Exclusion Criteria:

          -  Has received an investigational drug or other anti-cancer therapy within 3 weeks of
             the first dose of treatment or < 5 half-lives of that agent, whichever is shorter. Any
             toxicity from prior therapy must have recovered to < grade 1.

          -  Has a diagnosis of immunodeficiency or is receiving systemic steroid therapy or any
             other form of immunosuppressive therapy within 7 days prior to the first dose of trial
             treatment (only exception to this is the need for steroids for CNS metastases; see #6
             below). Inhaled, intra-articular, or topical steroids are permissible.

          -  Has a history of hypersensitivity to nivolumab.

          -  Has a known additional malignancy that is progressing or requires active treatment,
             the lack of which would pose a risk to the health of the subject, in the opinion of
             the investigator.

          -  Has known symptomatic central nervous system (CNS) metastases and/or carcinomatous
             meningitis. Subjects with previously treated brain metastases may participate provided
             they are stable without evidence of progression by imaging for at least four weeks
             after definitive intervention and using no more than the equivalent of dexamethasone
             2mg/d for the management of vasogenic edema, if necessary. This exception does not
             include carcinomatous meningitis, which is excluded regardless of clinical stability.

          -  Active autoimmune disease that has required systemic treatment in the past 2 years
             (i.e. with use of disease modifying agents, corticosteroids or immunosuppressive
             drugs). Replacement therapy (e.g., thyroxine, insulin, or physiologic corticosteroid
             replacement therapy [</= 10 mg/d equivalent of prednisone] for adrenal or pituitary
             insufficiency, etc.) is not considered a form of systemic treatment. Patients with
             previous grade III/IV toxicity from immunotherapy that led to treatment
             discontinuation are excluded.

          -  Has an active infection requiring systemic therapy.

          -  Has known psychiatric or substance abuse disorders that would interfere with
             cooperation with the requirements of the trial, in the opinion of the investigator.

          -  Is pregnant or breastfeeding.

          -  Has a known history of Human Immunodeficiency Virus (HIV), active Hepatitis B or
             Hepatitis C.

          -  Has received a live vaccine within 30 days of planned start of study therapy. Note:
             Seasonal influenza vaccines for injection are generally inactivated flu vaccines and
             are allowed; however intranasal influenza vaccines (e.g., Flu-Mist®) are live
             attenuated vaccines, and are not allowed