While the host immune system can recognize and respond to antigens-derived from solid cancers, tumors are rarely spontaneously rejected. The discovery of immune evasion mechanisms activated by solid cancers has led to the development of immunotherapies aimed at unleashing anti-tumor immunity. These immunotherapies are now first line treatment in many solid cancers and capable of inducing potent and durable responses in human patients. In contrast to solid tumors, much less is known about immune escape mechanisms utilized by hematopoietic malignancies, such as acute myeloid leukemia (AML). Here we discovered a unique immune evasion mechanism in AML bearing mice where leukemia-specific CD8+ T cells underwent abortive proliferation and were ultimately deleted from the host. T cell tolerance in mice with systemic leukemia was driven by immature splenic CD8α+ dendritic cells which acquire and cross-present leukemia-derived antigens to CD8+ T cells in a tolerogenic context. The activation of the innate immune system with a stimulator of interferon genes (STING) agonist was able to prevent the T cell tolerant state and cure mice with established AML. Thus our work provides the framework to clinically investigate therapeutic agents which activate the innate immune system in patients with AML.