Abstract Background Melanoma is one of the few types of cancer with an increasing annual incidence. While a number of immunotherapies for melanoma have been associated with significant clinical benefit, including high-dose IL-2 and cytotoxic T lymphocyte antigen 4 (CTLA-4) blockade, clinical response to either of these single agents has been limited to 11-20% of treated patients. Therefore, in this study, we sought to test the hypothesis that the combination of IL-2 and CTLA-4 blockade could mediate a more profound therapeutic response. Methods Here, B6 mice were challenged with poorly immunogenic B16 melanoma on day 0, and treated with CTLA-4 blocking antibody (100 μg/mouse) on days 3, 6, and 9, and IL-2 (100,000 units) twice daily on days 4–8, or both. Results A highly significant synergistic effect that delayed tumor growth and prolonged survival was demonstrated with the combination immunotherapy compared to either monotherapy alone. The therapeutic effect of combination immunotherapy was dependent on both CD8+ T and NK cells and co-depletion of these subsets (but not either one alone) abrogated the therapeutic effect. CTLA-4 blockade increased immune cell infiltration (including CD8+ T cells and NK cells) in the tumor and IL-2 reduced the proportion of highly differentiated/exhausted tumor-infiltrating NK cells. Conclusions These results have implications for the design of clinical trials in patients with metastatic melanoma and provide new insights into how the immune system may be mediating anti-tumor activity with combination IL-2 and CTLA-4 blockade in melanoma.