Vaccines against a variety of infectious diseases represent one of the great triumphs of medicine. The immune correlates of protection induced by most current vaccines seem to be mediated by long-lived humoral immune responses. By contrast, there are no currently available vaccines that are uniformly effective for diseases such as HIV, malaria and tuberculosis, in which the cellular immune response might be crucial in mediating protection. Here we examine the mechanisms by which long-lived cellular immune responses are generated and maintained in vivo. We then discuss current approaches for vaccination against diseases in which cellular immune responses are important for protection.