Background: Natural Killer (NK) cells are thought to protect from residual leukemic cells in patients receiving stem cell transplantation. However, multiple retrospective analyses of patient data have yielded conflicting conclusions regarding a putative role of NK cells and the essential NK cell recognition events mediating a protective effect against leukemia. Further, a NK cell mediated protective effect against primary leukemia in vivo has not been shown directly.Methodology/Principal Findings: Here we addressed whether NK cells have the potential to control chronic myeloid leukemia (CML) arising based on the transplantation of BCR-ABL1 oncogene expressing primary bone marrow precursor cells into lethally irradiated recipient mice. These analyses identified missing-self recognition as the only NK cell-mediated recognition strategy, which is able to significantly protect from the development of CML disease in vivo.Conclusion: Our data provide a proof of principle that NK cells can control primary leukemic cells in vivo. Since the presence of NK cells reduced the abundance of leukemia propagating cancer stem cells, the data raise the possibility that NK cell recognition has the potential to cure CML, which may be difficult using small molecule BCR-ABL1 inhibitors. Finally, our findings validate approaches to treat leukemia using antibody-based blockade of self-specific inhibitory MHC class I receptors.