Because existing therapeutic cancer vaccines provide only a limited clinical benefit, a different vaccination strategy is necessary to improve vaccine efficacy. We developed a nanoparticulate cancer vaccine by encapsulating a synthetic long peptide antigen within an immunologically inert nanoparticulate hydrogel (nanogel) of cholesteryl pullulan (CHP). After subcutaneous injection to mice, the nanogel-based vaccine was efficiently transported to the draining lymph node, and was preferentially engulfed by medullary macrophages but was not sensed by other macrophages and dendritic cells (so-called “immunologically stealth mode”). Although the function of medullary macrophages in T cell immunity has been unexplored so far, these macrophages effectively cross-primed the vaccine-specific CD8⁺ T cells in the presence of a Toll-like receptor (TLR) agonist as an adjuvant. The nanogel-based vaccine significantly inhibited in vivo tumor growth in the prophylactic and therapeutic settings, compared to another vaccine formulation using a conventional delivery system, incomplete Freund’s adjuvant. We also revealed that lymph node macrophages were highly responsive to TLR stimulation, which may underlie the potency of the macrophage-oriented, nanogel-based vaccine. These results indicate that targeting medullary macrophages using the immunologically stealth nanoparticulate delivery system is an effective vaccine strategy.