The protective effects of the tuberculosis vaccine Bacillus Calmette-Guerin (BCG) on unrelated infections are thought to be mediated by long-term metabolic changes and chromatin remodeling through histone modifications in innate immune cells such as monocytes, a process termed trained immunity. Here, we show that BCG induction of trained immunity in monocytes is accompanied by a strong increase in glycolysis and, to a lesser extent, glutamine metabolism, both in an in-vitro model and after vaccination of mice and humans. Pharmacological and genetic modulation of rate-limiting glycolysis enzymes inhibits trained immunity, changes that are reflected by the effects on the histone marks (H3K4me3 and H3K9me3) underlying BCG-induced trained immunity. These data demonstrate that a shift of the glucose metabolism toward glycolysis is crucial for the induction of the histone modifications and functional changes underlying BCG-induced trained immunity. The identification of these pathways may be a first step toward vaccines that combine immunological and metabolic stimulation.