Investigators will examine the safety of and immune responses to two vaccines expressing synthetic HIV proteins: NYVAC-B (a poxvirus), and rAd5 (an adenovirus). The study will compare responses in participants receiving NYVAC-B first, and rAd5 later, to those who receive rAd5 first, and NYVAC-B later. A different dose of rAd5 will be tested in each group.

In order to halt the HIV pandemic an effective vaccine must be developed. In this study, investigators will examine the safety and immune response to a prime-boost strategy using two different vaccine regimens, NYVAC-B and rAd5.

Eighty participants will be recruited to this study. Participants will be randomly assigned to one of four different groups (study arms). Each group will receive both study vaccines and placebo but at different times. All NYVAC-B vaccine doses will be the same, but the doses of the rAD5 vaccine will differ from group to group. Some participants in each group will receive only placebo. Participants will visit the study clinic about 13 times over the course of 12 months and be contacted for follow-up for 4 years.

All study injections will be given in the same upper arm area. There will be a total of four injections during the course of the study. After each injection, participants will need to stay in the clinic for at least 25 minutes to check for any adverse reactions. Additionally, participants will need to monitor their own health on the evening after the injection and for the next three evenings, by taking their temperature and making notes of any noticed side effects. Tools will be provided to accomplish both of these tasks. During these few days following the injection, study investigators will need to maintain contact with participants (the participant will specify the best mode of contact).

Certain clinical procedures will be performed during the course of this study including regular HIV testing and counseling, physical exams, collection of blood and urine, pregnancy tests if applicable, questions about health and medications, questions about HIV risk and sexual behaviors, and any personal problems or benefits participants may have experienced from participating in the study.

Inclusion Criteria:

• Willing and able to provide informed consent
• Assessment of understanding, including understanding of the Step Study results
• Willingness to receive HIV test results
• Amenable to HIV risk reduction counseling, committed to maintaining behavior consistent with low risk of HIV exposure through the last required protocol clinic visit
• Assessed by clinic staff as being "low risk" for HIV infection on the basis of sexual behaviors within the 12 months prior to enrollment. More information on this criterion is in the study protocol.
• Good general health
• Neutralizing antibody titers of Ad5 less than 1:18
• Hemoglobin count of 11.0 g/dL or more for female volunteers, and 13.0 g/dL or more for male volunteers
• White blood cell count of 3300 to 12000 cells/mm^3
• Total lymphocyte count of 800 cells/mm^3 or more
• Remaining differential either within institutional normal range or with site physician approval
• Platelets in the range of 125,000 to 550,000/mm^3
• Chemistry panel: Alanine aminotransferase (ALT), aspartate aminotransferase (AST), alkaline phosphatase, and creatinine values less than or equal to the institutional upper limits of normal
• HIV-uninfected
• Negative Hepatitis B surface antigen (HBsAg)
• Negative anti-Hepatitis C virus antibodies (anti-HCV), or negative HCV polymerase chain reaction (PCR) if the anti-HCV is positive
• Normal urine
• Not pregnant
• A volunteer who was born female must agree to consistently use effective contraception from at least 21 days prior to enrollment through the last protocol visit for sexual activity that could lead to pregnancy

Exclusion Criteria:

• Excessive alcohol use or chronic marijuana use, or any other illicit drug use within the 12 months prior to enrollment
• History of newly acquired syphilis, gonorrhea, non-gonococcal urethritis, herpes simplex virus type 2, chlamydia, pelvic inflammatory disease, trichomonas, mucopurulent cervicitis, epididymitis, proctitis, lymphogranuloma venereum, chancroid, within the 12 months prior to enrollment
• HIV vaccine received in a prior HIV vaccine trial. For potential participants who have received control/placebo in an HIV vaccine trial, documentation of the identity of the study control/placebo must be provided to the HVTN 078 PSRT, who will determine eligibility on a case-by-case basis.
• Immunosuppressive medications received within 168 days before first vaccination
• Blood products received within 120 days before first vaccination
• Immunoglobulin received within 60 days before first vaccination
• Live attenuated vaccines received within 30 days before first vaccination or scheduled within 14 days after first injection
• Any vaccines that are not live attenuated vaccines and were received within 14 days prior to first vaccination
• Allergy treatment with antigen injections within 30 days before first vaccination or that are scheduled within 14 days after first vaccination
• Investigational research agents received within 30 days before first vaccination
• Intent to participate in another study of an investigational research agent during the planned duration of the HVTN 078 study
• Current anti-tuberculosis (TB) prophylaxis or therapy
• Clinically significant medical condition, physical examination findings, clinically significant abnormal laboratory results, or past medical history with clinically significant implications for current health. More information on this criterion is in the study protocol.
• Any medical, psychiatric, or social condition, or occupational or other responsibility that, in the judgment of the investigator, would interfere with, or serve as a contraindication to, protocol adherence, assessment of safety or reactogenicity, or a participant's ability to give informed consent
• Serious adverse reactions to vaccines including anaphylaxis and related symptoms such as hives, respiratory difficulty, angioedema, and/or abdominal pain
• Active syphilis infection
• Allergy to eggs and/or egg products
• History of, or known active cardiac disease
• Participants who have 2 or more specified cardiac risk factors as defined by the study. More information on this criterion is in the study protocol.
• ECG with clinically significant findings. More information on this criterion is in the study protocol.
• Autoimmune disease
• Immunodeficiency
• Asthma other than mild, well-controlled asthma.
• Diabetes mellitus type 1 or type 2, including cases controlled with diet alone
• Thyroidectomy, or thyroid disease
• Angioedema
• Hypertension
• Body mass index (BMI) equal to 40 and above or 35 and above with at least two of the following: systolic blood pressure greater than 140 mm Hg, diastolic blood pressure more than 90 mm Hg, current smoker, known hyperlipidemia
• Bleeding disorder
• Malignancy
• Seizure disorder
• Asplenia
• Psychiatric condition that precludes compliance with the protocol
• Pregnant or breastfeeding