Although the Bacille-Calmette-Guérin (BCG) vaccine is used to prevent tuberculosis, it also offers protection against a diverse range of non-mycobacterial infections. However, the underlying protective mechanisms in humans are not yet fully understood. Here, we surveyed at single-cell resolution the gene expression and chromatin landscape of human bone marrow, aspirated before and 90 days after BCG vaccination or placebo. We showed that BCG alters both the gene expression and epigenetic profiles of human hematopoietic stem and progenitor cells (HSPCs). Changes in gene expression occurred primarily within uncommitted stem cells. By contrast, changes in chromatin accessibility were most prevalent within differentiated progenitor cells at sites influenced by Kruppel-like factor (KLF) and early growth response (EGR) transcription factors and were highly correlated (r > 0.8) with the interleukin (IL)-1β secretion capacity of paired peripheral blood mononuclear cells (PBMCs). Our findings shed light on BCG vaccination's profound and lasting effects on HSPCs and its influence on innate immune responses and trained immunity.