New therapies are needed that target breast cancer metastases. In previous studies, we have shown that vaccination with pcDNA3.1-Mage-b DNA vaccine is effective against breast cancer metastases. In the study presented here, we have further enhanced the efficacy of Mage-b vaccination through the improved delivery of the vaccine using recombinant Listeria monocytogenes (LM). Three overlapping fragments of Mage-b as well as the complete protein-encoding region of Mage-b have been expressed as a fusion protein with a truncated non-cytolytic form of listeriolysin O (LLO) in recombinant LM. These different Mage-b vaccine strains were preventively tested for their efficacy against breast cancer metastases in a syngeneic mouse tumour model 4T1. The LM-LLO-Mage-b/2nd, expressing position 311-660 of the cDNA of Mage-b, was the most effective vaccine strain against metastases in the 4T1 mouse breast tumour model. Vaccination with LM-LLO-Mage-b/2nd dramatically reduced the number of metastases by 96% compared with the saline group and by 88% compared with the vector control group (LM-LLO), and this correlated with strong Mage-b-specific CD8 T-cell responses in the spleen, after restimulation with Mage-b. However, no effect of LM-LLO-Mage-b/2nd was observed on 4T1 primary tumours, which may be the result of a complete absence of Mage-b-specific immune responses in the draining lymph nodes. Vaccination with LM-LLO-Mage-b/2nd could be an excellent follow-up after removal of the primary tumour, to eliminate metastases and residual tumour cells.