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.