Issues of quantity, quality and location impact the ability of CD8 T cells to mediate protection from infection. These issues are considered in light of human immunodeficiency virus (HIV)/simian immunodeficiency virus (SIV) vaccination. Methods are reviewed that result in 100- to 1000-fold higher frequencies of vaccine-specific memory CD8 T cells than that achieved by current HIV/SIV vaccine approaches. Data demonstrating that location within mucosal tissues has a direct impact on memory CD8 T-cell function are discussed. Arguments are made that establishing memory CD8 T cells within mucosal sites of transmission, a priori to natural infection, may be essential for conferring optimal and rapid protection. Lastly, it is proposed that heterologous prime-boost vaccination with recombinant live replicating vectors, which has the potential to induce tremendous numbers of cytolytic memory CD8 T cells within mucosal tissues, would provide a far more stringent test of the hypothesis that memory CD8 T cells could, in principal, form the basis for a preventative HIV vaccine.