Leukemias are clonal proliferative disorders arising from immature leukocytes in the bone marrow. While the advent of targeted therapies has improved survival in certain subtypes, relapse after initial therapy is a major problem. Dendritic cell (DC) vaccination has the potential to induce tumor-specific T cells providing long-lasting, anti-tumor immunity. This approach has demonstrated safety but limited clinical success until recently, as DC vaccination faces several barriers in both solid and hematological malignancies. Importantly, vaccine-mediated stimulation of protective immune responses is hindered by the aberrant production of immunosuppressive factors by cancer cells which impede both DC and T cell function. Leukemias present the additional challenge of severely disrupted hematopoiesis owing to both cytogenic defects in hematopoietic progenitors and an abnormal hematopoietic stem cell niche in the bone marrow; these factors accentuate systemic immunosuppression and DC malfunction. Despite these obstacles, several recent clinical trials have caused great excitement by extending survival in Acute Myeloid Leukemia (AML) patients through DC vaccination. Here, we review the phenotype and functional capacity of DCs in leukemia and approaches to harness DCs in leukemia patients. We describe the recent clinical successes in AML and detail the multiple new strategies that might enhance prognosis in AML and other leukemias.