Publication of the first efficacious large-scale HIV vaccine trial in 2009 prompted fresh hope that design of a protective vaccine against HIV may be achievable. In this review we explore the difficult task of eliciting protective immune responses to HIV and highlight the hurdles that vaccine design must still overcome.