HIV-1 is the leading cause of death in sub-Saharan Africa, responsible for one in five deaths in the region. Although potent antiretroviral therapy has had a huge impact on HIV-associated morbidity and mortality in economically advantaged countries, it is beyond the reach of most infected people in the world. The development of an effective HIV vaccine would be a huge step towards stopping the pandemic, but an important precondition for such a vaccine is that it must induce a host immune response that can protect the host from HIV acquisition or disease progression. This article reviews the evidence that protective host immune responses do exist, either in highly exposed, persistently seronegative (HEPS) subjects or in HIV-1-infected long-term non-progressors (LTNPs), as well as efforts to reproduce putative protective immunity in animal vaccine models. HIV-1-specific cellular responses are a key to viral control in infected subjects, but generally fail in the long term. This suggests that the goal of a preventive HIV-1 vaccine should be sterile immunity, rather than improved virus control after infection. Achieving this goal will at least require the induction of HIV-1-specific cellular immune responses at the site of initial viral contact (generally the genital tract), perhaps in combination with HIV-1-specific neutralising antibody.