Prime-boost vaccine strategies are aimed at inducing different types of immune responses and enhancing the overall immune response, a result that may not occur with a single type of vaccine. This trial will evaluate the safety and immunogenicity of an HIV multi-epitope peptide cytotoxic T lymphocyte (HIV CTL MEP) vaccine developed as part of a prime-boost strategy and designed to be administered in combination with an HIV DNA vaccine. The HIV CTL MEP vaccine is a mixture of four synthetic peptides, each containing one of three different HIV CTL epitopes derived from env or gag. The use of multiple conserved CTL epitopes will address the extraordinary diversity found among HIV strains. The vaccine is administered with RC529-SE, an analogue of monophosphoryl lipid A. The vaccine/adjuvant combination will be evaluated with or without coadministration of granulocyte-macrophage colony-stimulating factor (GM-CSF). Participants will be randomly assigned to receive either the vaccine with the RC529-SE adjuvant, the vaccine with both adjuvants (RC529-SE and GM-CSF), or a placebo. The vaccine, adjuvants, and placebo will all be given as an injection into the upper arm. Participants will have 11 study visits. Study visits will include a physical exam, medical interview, and blood and urine tests. Participants will receive an injection at three of these visits: study entry and Months 1 and 3. Participants will be followed for 1 year after the last injection.
Inclusion Criteria: * HIV uninfected * Willing to receive HIV test results * Good general health * One of the following major histocompatibility (MHC) alleles: HLA A3, B7, or B8 * Acceptable methods of contraception for females of reproductive potential * Hepatitis B surface antigen negative * Anti-hepatitis C virus antibody (anti-HCV) negative or negative HCV PCR if anti-HCV is positive * Access to participating site and available for follow-up during the 15 month study Exclusion Criteria: * HIV vaccines or placebos in prior HIV vaccine trial * Immunosuppressive medications within 168 days prior to first study vaccine administration * Blood products within 120 days prior to first study vaccine administration * Immunoglobulin within 60 days prior to first study vaccine administration * Live attenuated vaccines within 30 days prior to first study vaccine administration * Investigational research agents within 30 days prior to first study vaccine administration * Subunit or killed vaccines within 14 days prior to first study vaccine administration * Current tuberculosis prophylaxis or therapy * Serious adverse reaction to a vaccine. A person who had an adverse reaction to pertussis vaccine as a child is not excluded. * Hypersensitivity to egg products or yeast-derived products * Autoimmune disease or immunodeficiency * Active syphilis * Unstable asthma * Type 1 or Type 2 diabetes mellitus * Thyroid disease requiring treatment in the past 12 months * Serious angioedema within the past 3 years * Uncontrolled hypertension * Bleeding disorder * Malignancy unless it has been surgically removed and, in the opinion of the investigator, is not likely to recur during the study period * Seizure disorder requiring medication within the past 3 years * Asplenia * Mental illness that would interfere with compliance with the protocol * Other conditions that, in the judgment of the investigator, would interfere with the study * Pregnant or breast-feeding