The dogma that adaptive immunity is the only arm of the immune response with memory capacity has been recently challenged by several studies demonstrating evidence for memory-like innate immune training. However, the underlying mechanisms and location for generating such innate memory responses in vivo remain unknown. Here, we show that access of Bacillus Calmette-Guérin (BCG) to the bone marrow (BM) changes the transcriptional landscape of hematopoietic stem cells (HSCs) and multipotent progenitors (MPPs), leading to local cell expansion and enhanced myelopoiesis at the expense of lymphopoiesis. Importantly, BCG-educated HSCs generate epigenetically modified macrophages that provide significantly better protection against virulent M. tuberculosis infection than naïve macrophages. By using parabiotic and chimeric mice, as well as adoptive transfer approaches, we demonstrate that training of the monocyte/macrophage lineage via BCG-induced HSC reprogramming is sustainable in vivo. Our results indicate that targeting the HSC compartment provides a novel approach for vaccine development.