The focus of most current HIV-1 vaccine development is on antibody-based approaches. This is because certain antibody responses correlated with protection from HIV-1 acquisition in the RV144 phase III trial, and because a series of potent and broad spectrum neutralizing antibodies have been isolated from infected individuals. Taken together, these two findings suggest ways forward to develop a neutralizing antibody-based vaccine. However, understanding of the correlates of protection from disease in HIV-1 and other infections strongly suggests that we should not ignore CTL-based research. Here we review recent progress in the field and highlight the challenges implicit in HIV-1 vaccine design and some potential solutions.