Combination therapies for melanoma that target immune-regulatory networks are entering clinical practice, and more are under investigation in preclinical or clinical studies. Adenosine plays a key role in regulating melanoma progression. We investigated the effectiveness of cytotoxic T lymphocyte-associated antigen 4 (CTLA-4) antibody (mAb) in combination with either modulators of adenosine receptors (AR) activation or an inhibitor of adenosine production in a murine model of melanoma. We found that treatment with APCP, selective inhibitor of the adenosine-generating nucleotidase CD73, enhanced the activity of anti-CTLA4 mAb, by improving tumor immune response. Blockade of the adenosine A2a receptor (A2aR), which plays a critical role in the regulation of T-cell functions, significantly reduced melanoma growth. Most importantly, combination therapy including an A2aR antagonist with anti-CTLA4 mAb markedly inhibited tumor growth and enhanced anti-tumor immune responses. Targeting A3R and CTLA4 was not as effective in limiting melanoma growth as targeting A2aR. These data suggest that the efficacy of anti-CTLA4 melanoma therapy may be improved by targeting multiple mechanisms of immune suppression within tumor tissue, including CD73 or A2a receptor.