With the advent of checkpoint blockade therapies, immunotherapy is now a critical modality for the treatment of some cancers. While some patients respond well to checkpoint blockade, many do not, necessitating the need for other forms of therapy. Vaccination against malignancy has been a long sought goal of science. For cancers holding a microbial etiology, vaccination has been highly effective in reducing the incidence of disease. However, vaccination against established malignancy has been largely disappointing. In this review, we discuss efforts to develop diverse vaccine modalities in the treatment of cancer with a particular focus on melanoma. Recent work has suggested that vaccines targeting patient-specific tumor mutations may be more relevant than those targeting unmutated proteins. Nonetheless, tumor cells utilize many strategies to evade host immunity. It is likely that the full potential of cancer vaccination will only be realized when vaccines are combined with other therapies targeting tumor immunoevasive mechanisms. By modulating inhibitory molecules, regulatory immune cells, and the metabolic resources and demands of T cells, scientists and clinicians can ensure vaccine-stimulated T cells are fully functional within the immunosuppressive tumor microevironment.