Cells of the innate immune system are essential for host defenses against primary microbial pathogen infections, yet their involvement in effective memory responses of vaccinated individuals has been poorly investigated. Here we show that memory T cells instruct innate cells to become potent effector cells in a systemic and a mucosal model of infection. Memory T cells controlled phagocyte, dendritic cell, and NK or NK T cell mobilization and induction of a strong program of differentiation, which included their expression of effector cytokines and microbicidal pathways, all of which were delayed in nonvaccinated hosts. Disruption of IFN-γ signaling in Ly6C⁺ monocytes, dendritic cells, and macrophages impaired these processes and the control of pathogen growth. These results reveal how memory T cells, through rapid secretion of IFN-γ, orchestrate extensive modifications of host innate immune responses that are essential for effective protection of vaccinated hosts.