Major histocompatibility complex class I (MHC-I) presented peptide epitopes provide a ‘window’ into the changes occurring in a cell. Conventionally, these peptides are generated by proteolysis of endogenously synthesized proteins in the cytosol, loaded onto MHC-I molecules, and presented on the cell surface for surveillance by CD8⁺ T cells. MHC-I restricted processing and presentation alerts the immune system to any infectious or tumorigenic processes unfolding intracellularly and provides potential targets for a cytotoxic T cell response. Therefore, therapeutic vaccines based on MHC-I presented peptide epitopes could, theoretically, induce CD8⁺ T cell responses that have tangible clinical impacts on tumor eradication and patient survival. Three major methods have been used to identify MHC-I restricted epitopes for inclusion in peptide-based vaccines for cancer: genetic, motif prediction and, more recently, immunoproteomic analysis. Although the first two methods are capable of identifying T cell stimulatory epitopes, these have significant disadvantages and may not accurately represent epitopes presented by a tumor cell. In contrast, immunoproteomic methods can overcome these disadvantages and identify naturally processed and presented tumor associated epitopes that induce more clinically relevant tumor specific cytotoxic T cell responses. In this review, we discuss the importance of using the naturally presented MHC-I peptide repertoire in formulating peptide vaccines, the recent application of peptide-based vaccines in a variety of cancers, and highlight the pros and cons of the current state of peptide vaccines.