HIV vaccines may help the immune systems of HIV infected patients better control the virus. The goal of this study is to determine whether patients on anti-HIV medications can stop taking those medications if they receive an HIV vaccine. While taking anti-HIV medications, participants will receive either an HIV vaccine or a placebo. Participants will then stop taking their anti-HIV medications and the study will compare the viral loads of participants who received the vaccine with the viral loads of participants who received the placebo.

Primary study hypotheses: 1)The Week 12 and Week 16 post-ART interruption geometric mean HIV-1 RNA levels will be lower among participants who had received MRK Ad5 vaccine prior to ART interruption than among participants who received placebo; 2) the time averaged area under the curve of the log10 HIV-1 RNA copies/ml versus day function in the 16 week post-ART interruption step will be lower among participants who received the MRK Ad5 vaccine prior to ART interruption than among participants who receive placebo.

Antiretroviral therapy (ART) has a significant impact on HIV disease; however, HIV cannot be cured with current drug regimens. While the majority of patients initially benefit from ART, drug regimens subsequently fail for many patients due to drug resistance, poor adherence, or toxicity. If given while HIV replication is kept in check by ART, an HIV vaccine may be able to generate an effective long-term immune response capable of controlling the virus, even if ART is discontinued.

The MRK Ad5 HIV-1 gag vaccine uses a replication-defective adenovirus vector and has been found safe in clinical trials of both HIV infected and HIV uninfected adults. This study will evaluate the ability of immunization with the MRK Ad5 HIV-1 gag vaccine to control HIV replication in individuals undergoing treatment interruption. The study will enroll individuals whose HIV replication has been successfully suppressed with ART for at least 2 years.

Participants in this study will be randomly assigned to receive either vaccine or placebo. Both vaccine and placebo will be injected into the upper arm muscle. Participants will take their antiretroviral medications during the first 3 months of the study. Injections will be given on Day 1, Week 4, and Week 26. A study nurse will call participants 1 or 2 days after each injection and participants will be asked to fill out a card with any reactions they have to the injections. About 3 months after the third injection, participants will stop taking their antiretroviral medications for 4 months. Participants will have study visits every 2 to 3 weeks while off medication. After 4 months, participants will have the option of restarting antiretroviral medications or continuing without medication. Participants will then have study visits every 2 months for 8 months. Study visits will include physical exams and blood collection.

All participants will continue to see their primary care provider for HIV treatment and will be restarted on antiretroviral medications if clinically indicated. Participants or their primary care provider will be contacted by phone for updates every 6 months for an additional 3.5 years.

Inclusion Criteria

• HIV infected
• On a stable antiretroviral medication regimen (no changes to treatment within 4 weeks of study entry)
• Viral load less than 50 copies/ml
• Viral suppression for 2 years prior to study entry (documented viral loads less than 500 copies/ml)
• CD4 count of 500 cells/mm3 or greater
• Ad5 neutralizing antibody less than 200 units at screening
• Willing to stop antiretroviral medications for at least 16 weeks post-vaccination
• Hepatitis B surface antigen negative
• Weight more than 110 lbs
• Willing to use acceptable methods of contraception

Exclusion Criteria

• Two consecutive viral loads of 500 copies/ml or greater at least 14 days apart during the 24 months prior to study entry
• Two consecutive CD4 counts less than 200 cells/mm3 before starting antiretroviral medications
• History of anaphylaxis
• Allergy to vaccine components
• History of cardiac, pulmonary, gastrointestinal, hepatic, renal, pancreatic, or neurologic disease which, in the opinion of the study official, will compromise study participation
• Pregnancy or breastfeeding
• Contraindication to intramuscular injection, such as anticoagulant therapy or thrombocytopenia
• Immune globulin or blood products within 3 months prior to study entry
• Live vaccine within 30 days prior to study entry
• Inactivated vaccine within 14 days prior to study entry
• Previous HIV vaccine
• History of an AIDS-defining illness. Patients with a history of Kaposi's sarcoma limited to the skin may participate.
• Currently taking drugs or other substances not approved by the FDA. Patients may be on antiretroviral agents not yet approved by the FDA as part of a clinical trial or through an expanded access program.
• Immunomodulatory agents (interferon, IL-2, GM-CSF, systemic corticosteroids, etc.) within 30 days prior to study entry
• Active alcohol or substance abuse which may interfere with the study