Colorectal cancer (CRC) remains refractory to most immunotherapies, with cancer vaccines failing due to an immunosuppressive tumor microenvironment. Here, we show that beta-glucan-induced trained immunity overcomes these barriers by reprogramming macrophages through H3K4me3-dependent epigenetic modifications and metabolic rewiring. In female mice vaccinated with peptide-coated adenovirus-based vaccine PeptiCrad, training enhances glycolysis with creatine metabolism sustaining CXCL9/10 production, enabling macrophages to recruit NK cells via CXCR3. In turn, NK cells produce CCL5, driving cDC1 infiltration and antigen presentation, which together amplify effector memory CD8(+) T cell responses. Moreover, with human peripheral blood mononuclear cells and CRC patient-derived organoids, trained macrophages boost NK migration, antigen-specific T cell activation, and tumor killing. These findings highlight trained immunity as a powerful adjuvant to reinvigorate colorectal cancer vaccination.