The A_2A adenosine receptor plays a critical and non-redundant role in suppressing inflammation at sites of hypoxia and tissue damage. The tumor microenvironment has high levels of adenosine as a result of hypoxia and ectopic expression of enzymes responsible for the generation of extracellular adenosine. Thus, we sought to determine the ability of A_2A receptor null mice to immunologically reject tumors. We observed that mice lacking the A_2A adenosine receptor showed significantly delayed growth of lymphoma cells when compared to WT mice. Furthermore, when immunized with a low dose of tumor or with an irradiated GM-CSF–secreting tumor vaccine, A_2A receptor null mice showed significantly enhanced protection from a subsequent high-dose challenge from both immunogenic and poorly immunogenic tumor lines. This increase in protection was accompanied by an increase in the number of tumor-antigen-specific CD8 T cells at the vaccine-site draining lymph node. Finally, we found that A_2A receptor null mice displayed more robust anti-tumor responses than WT mice when they were treated with a soluble B7-DC/Fc fusion protein designed to antagonize B7-H1-mediated co-inhibition. This combinatorial immunotherapy strategy could also be recapitulated with pharmacological A_2A receptor blockade paired with B7-DC/Fc administration. In light of these data, we believe that blockade of the A_2A adenosine receptor is an attractive target for tumor immunotherapy that synergizes with other immunomodulatory approaches currently in clinical trials.