Herpes simplex viruses (HSV) types 1 and 2 are ubiquitous. They both cause genital herpes, occasionally severe disease in the immunocompromised, and facilitate much HIV acquisition globally. Despite more than 60 years of research, there is no licensed prophylactic HSV vaccine and some doubt as to whether this can be achieved. Nevertheless, a previous HSV vaccine candidate did have partial success in preventing genital herpes and HSV acquisition and another immunotherapeutic candidate reduced viral shedding and recurrent lesions, inspiring further research. However, the entry pathway of HSV into the anogenital mucosa and the subsequent cascade of immune responses need further elucidation so that these responses could be mimicked or improved by a vaccine, to prevent viral entry and colonization of the neuronal ganglia. For an effective novel vaccine against genital herpes the choice of antigen and adjuvant may be critical. The incorporation of adjuvants of the vaccine candidates in the past, may account for their partial efficacy. It is likely that they can be improved by understanding the mechanisms of immune responses elicited by different adjuvants and comparing these to natural immune responses. Here we review the history of vaccines for HSV, those in development and compare them to successful vaccines for chicken pox or herpes zoster. We also review what is known of the natural immune control of herpes lesions, via interacting innate immunity and CD4 and CD8 T cells and the lessons they provide for development of new, more effective vaccines.