In 2010, the US FDA approved the first therapeutic cancer vaccine for the treatment of castration refractory prostate cancer - sipuleucel-T. Prostate cancer is an ideal model for cancer vaccine development based on the ready demonstration of humoral and cellular immunity to a range of cancer antigens as well as often slow progression which means that patients who are otherwise well may have a radiologically evaluable minor progression, after conventional treatment and can undergo vaccine therapy over sufficient periods of time, so as to allow the generation of a robust antitumor response. The association of prostate cancer with one of the few serum cancer biomarkers in general use has also allowed assessment of response and risk stratification of patients. In this review, we will examine key aspects of the evolution of prostate cancer vaccines, which provides an accurate prototype for other cancers, and the challenges we face.