Breast cancer affects roughly one in eight women over their lifetime and is a leading cause of cancer-related death in women. While outcomes have improved in recent years, prognosis remains poor for patients who present with either disseminated disease or aggressive molecular subtypes. Cancer immunotherapy has revolutionized the treatment of several cancers, with therapeutic vaccines aiming to direct the cytotoxic immune program against tumor cells showing particular promise. However, these results have yet to translate to breast cancer, which remains largely refractory from such approaches. Recent evidence suggests that the breast tumor microenvironment (TME) is an important and long understudied barrier to the efficacy of therapeutic vaccines. Through an improved understanding of the complex and biologically diverse breast TME, it may be possible to advance new combination strategies to render breast carcinomas sensitive to the effects of therapeutic vaccines. Here, we discuss past and present efforts to advance therapeutic vaccines in the treatment of breast cancer, the molecular mechanisms through which the TME contributes to the failure of such approaches, as well as the potential means through which these can be overcome.