The anti-tuberculosis-vaccine Bacillus Calmette-Guerin (BCG) is the most widely used vaccine in the world. In addition to its effects against tuberculosis, BCG vaccination also induces non-specific beneficial effects against certain forms of malignancy and against infections with unrelated pathogens. It has been recently proposed that the non-specific effects of BCG are mediated through epigenetic reprogramming of monocytes, a process called trained immunity. In the present study we demonstrate that autophagy contributes to trained immunity induced by BCG. Pharmacologic inhibition of autophagy blocked trained immunity induced in vitro by stimuli such as beta-glucans or BCG. Single nucleotide polymorphisms (SNPs) in the autophagy genes ATG2B (rs3759601) and ATG5 (rs2245214) influenced both the in vitro and in vivo training effect of BCG upon restimulation with unrelated bacterial or fungal stimuli. Furthermore, pharmacologic or genetic inhibition of autophagy blocked epigenetic reprogramming of monocytes at the level of H3K4 trimethylation. Finally, we demonstrate that rs3759601 in ATG2B correlates with progression and recurrence of bladder cancer after BCG intravesical instillation therapy. These findings identify a key role of autophagy for the nonspecific protective effects of BCG.