Immunotherapies targeting the programmed death 1 (PD-1) coinhibitory receptor have shown great promise for a subset of patients with cancer. However, robust and safe combination therapies are still needed to bring the benefit of cancer immunotherapy to broader patient populations. To search for an optimal strategy of combinatorial immunotherapy, we have compared the antitumor activity of the anti–4-1BB/anti–PD-1 combination with that of the anti–PD-1/anti–LAG-3 combination in the poorly immunogenic B16F10 melanoma model. Pronounced tumor inhibition occurred only in animals receiving anti–PD-1 and anti–4-1BB concomitantly, while combining anti–PD-1 with anti–LAG-3 led to a modest degree of tumor suppression. The activity of the anti–4-1BB/anti–PD-1 combination was dependent on IFNγ and CD8⁺ T cells. Both 4-1BB and PD-1 proteins were elevated on the surface of CD8⁺ T cells by anti–4-1BB/anti–PD-1 cotreatment. In the tumor microenvironment, an effective antitumor immune response was induced as indicated by the increased CD8⁺/Treg ratio and the enrichment of genes such as Cd3e, Cd8a, Ifng, and Eomes. In the spleen, the combination treatment shaped the immune system to an effector/memory phenotype and increased the overall activity of tumor-specific CD8⁺ CTLs, reflecting a long-lasting systemic antitumor response. Furthermore, combination treatment in C57BL/6 mice showed no additional safety signals, and only minimally increased severity of the known toxicity relative to 4-1BB agonist alone. Therefore, in the absence of any cancer vaccine, anti–4-1BB/anti–PD-1 combination therapy is sufficient to elicit a robust antitumor effector/memory T-cell response in an aggressive tumor model and is therefore a candidate for combination trials in patients. Cancer Immunol Res; 3(2); 149–60. ©2014 AACR.