Cytotoxic T lymphocyte (CTL) responses are important to the initial decrease in HIV viral load seen in the first several months after acute infection. These beneficial CTL responses diminish with disease progression and cannot be recovered with antiretroviral therapy alone. Recent studies suggest a vaccine may help restore CTL responses. This study tests the effectiveness of the C4-V3 vaccine, a synthetic peptide vaccine representing 4 epitopes from HIV gp120, including an HLA B7-restricted CTL epitope. Administering IL-12, an immunostimulatory cytokine, in conjunction with C4-V3 may enhance HIV-1 specific immune responses and global immune function.