Abstract Correlates of immune protection from HIV vaccines remain undefined. The first HIV vaccine efficacy trial in the US and Europe VAX004, was designed to assess whether rgp120 envelope subunits (AIDSVAX B/B, VaxGen) can induce partial or complete protection from HIV-1 infection. No effectiveness in the reduction of either the acquisition of infection or levels of plasma viremia after HIV infection was noted. We found evidence of vaccine-specific CD8+ T cells in volunteers who received the vaccine, regardless of behavioral risk. Surprisingly, the CD8-response is significantly higher in participants who would go on to contract HIV infection. These results suggest that AIDSVAX immunization may boost preexisting immune responses—due to pre-infection exposure, and a vaccine-induced immune profile may serve as a biological marker for HIV susceptibility.