Shigella is an important human pathogen that has no licensed vaccine. Despite decades of seminal work suggesting that its pathogenicity relies on inflammatory cell death of macrophages, the in vivo role of macrophages in controlling Shigella infection remains poorly understood. Here, we use a zebrafish model of innate immune training to investigate the antibacterial role of macrophages following a non-lethal Shigella infection. We found that macrophages are crucial for zebrafish larvae survival during secondary Shigella infection. Consistent with signatures of trained immunity, we demonstrate that bacteria are cleared during training and that protection is independent of the secondary infection site. We show that following Shigella training, macrophages have altered mono- and tri-methylation on lysine 4 in histone 3 (H3K4me1/me3) deposition and shift toward a pro-inflammatory state, characterized by increased tumor necrosis factor alpha (TNF-α) expression and antibacterial reactive oxygen species (ROS) production. We conclude that macrophages are epigenetically reprogrammed by Shigella infection to enhance pro-inflammatory and protective responses.