A vaccine inducing protective immunity in mucosal tissues and secretions may stop or limit HIV infection. Although cytotoxic T lymphocytes (CTLs) are clearly associated with control of viral replication in HIV and simian immunodeficiency virus (SIV) infections, there are examples of uncontrolled viral replication in the face of strong CD8+ T-cell responses. The number of functions, breadth, avidity, and magnitude of CTL response are likely to be important factors in the effectiveness of anti-HIV T-cell response, but the location and persistence of effector CD8+ T cells are also critical factors. Although the only HIV vaccine clinical trial targeting cellular immunity to prevent HIV infection failed, vaccine strategies using persistent agents against pathogenic mucosal challenge in macaque models are showing unique success. Thus, the key to control the initial focus of viral replication at the portal of entry may rely on the continuous generation of effector CTL responses at mucosal level.