This study is to find out if the combination of CC-122 (an investigational agent) and Nivolumab will enhance the anti-cancer activity and prevent T-cell exhaustion (T-cells are responsible for maintaining the body's immune response).

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 [](streamdown:incomplete-link)

Adverse events collected from time of informed consent to 30 days after study participation, approximately 2.5 years.