The A2b receptor (A2bR) belongs to the adenosine receptor family. Emerging evidence suggest that A2bR is implicated in tumor progression in some murine tumor models, but the therapeutic potential of targeting A2bR in melanoma has not been examined. This study first shows that melanoma-bearing mice treated with Bay 60-6583, a selective A2bR agonist, had increased melanoma growth. This effect was associated with higher levels of immune regulatory mediators interleukin-10 (IL-10) and monocyte chemoattractant protein 1 (MCP-1) and accumulation of tumor-associated CD11b positive Gr1 positive cells (CD11b(+)Gr1(+)) myeloid-derived suppressor cells (MDSCs). Depletion of CD11b(+)Gr1(+) cells completely reversed the protumor activity of Bay 60-6583. Conversely, pharmacological blockade of A2bR with PSB1115 reversed immune suppression in the tumor microenvironment, leading to a significant melanoma growth delay. PSB1115 treatment reduced both levels of IL-10 and MCP-1 and CD11b(+)Gr1(+) cell number in melanoma lesions. These effects were associated with higher frequency of tumor-infiltrating CD8 positive (CD8(+)) T cells and natural killer T (NKT) cells and increased levels of T helper 1 (Th1)-like cytokines. Adoptive transfer of CD11b(+)Gr1(+) cells abrogated the antitumor activity of PSB1115. These data suggest that the antitumor activity of PSB1115 relies on its ability to lower accumulation of tumor-infiltrating MDSCs and restore an efficient antitumor T cell response. The antitumor effect of PSB1115 was not observed in melanoma-bearing nude mice. Furthermore, PSB1115 enhanced the antitumor efficacy of dacarbazine. These data indicate that A2bR antagonists such as PSB1115 should be investigated as adjuvants in the treatment of melanoma.