Immunological memory in vertebrates is often exclusively attributed to T and B cell function. Recently it was proposed that the enhanced and sustained innate immune responses following initial infectious exposure may also afford protection against reinfection. Testing this concept of "trained immunity," we show that mice lacking functional T and B lymphocytes are protected against reinfection with Candida albicans in a monocyte-dependent manner. C. albicans and fungal cell wall β-glucans induced functional reprogramming of monocytes, leading to enhanced cytokine production in vivo and in vitro. The training required the β-glucan receptor dectin-1 and the noncanonical Raf-1 pathway. Monocyte training by β-glucans was associated with stable changes in histone trimethylation at H3K4, which suggests the involvement of epigenetic mechanisms in this phenomenon. The functional reprogramming of monocytes, reminiscent of similar NK cell properties, supports the concept of "trained immunity" and may be employed for the design of improved vaccination strategies.