Trained immunity is a long-term memory of innate immune cells, generating an improved response upon reinfection. Shigella is an important human pathogen and inflammatory paradigm for which there is no effective vaccine. Using zebrafish larvae, we demonstrate that after Shigella training, neutrophils are more efficient at bacterial clearance. We observe that Shigella-induced protection is nonspecific and has differences with training by BCG and β-glucan. Analysis of histone ChIP-seq on trained neutrophils revealed that Shigella training deposits the active H3K4me3 mark on promoter regions of 1612 genes, dramatically changing the epigenetic landscape of neutrophils toward enhanced microbial recognition and mitochondrial ROS production. Last, we demonstrate that mitochondrial ROS plays a key role in enhanced antimicrobial activity of trained neutrophils. It is envisioned that signals and mechanisms we discover here can be used in other vertebrates, including humans, to suggest new therapeutic strategies involving neutrophils to control bacterial infection.