The cancer microenvironment is constituted of non-transformed host stromal cells such as endothelial cells, fibroblasts, various immune cells, and a complex extra-cellular matrix secreted by both the normal and neoplastic cells embedded in it. The importance of the microenvironment and its potential in cancer therapy is just being established. Among modalities that target the microenvironment, cancer vaccine is a unique strategy which is aimed to elicit specific immunity against components in the microenvironment. Most, if not all, components can be targeted by the vaccines. The most extensively studied are the endothelial cells, fibroblasts and macrophages as well as ECM. Vaccines are in development for each of them. All the vaccines were proved to be effective at providing protective or therapeutic anti-tumor effects in the pre-clinical models. A few of them have been tested in the clinical trials. The mechanisms of the vaccines were mainly related to the cellular immune response such as CD8+ cytotoxic T cells, and in some instances CD4+ Th cells were involved as well. The present review also discussed the hurdles associated with the microenvironment-based vaccines such as the selection of suitable patients with appropriate biomarkers. With the rapid increase of our knowledge in the cancer microenvironment, the proof-of-concept of microenvironment-based cancer vaccines will surely expand our armamentarium against cancer.