All studies using human serotype 5 Adenovirus (Ad) vectors must address two major obstacles: safety and the presence of pre-existing neutralizing antibodies. Helper-Dependent (HD) Ads have been proposed as alternative vectors for gene therapy and vaccine development because they have an improved safety profile. To evaluate the potential of HD-Ad vaccines, we compared replication-competent (RC), first-generation (FG) and HD vectors for their ability to induce immune responses in mice. We show that RC-Ad5 and HD-Ad5 vectors generate stronger immune responses than FG-Ad5 vectors. HD-Ad5 vectors gave lower side effects than RC or FG-Ad, producing lower levels of tissue damage and anti-Ad T cell responses. Also, HD vectors have the benefit of being packaged by all subgroup C serotype helper viruses. We found that HD serotypes 1, 2, 5, and 6 induce anti-HIV responses equivalently. By using these HD serotypes in heterologous succession we showed that HD vectors can be used to significantly boost anti-HIV immune responses in mice and in FG-Ad5-immune macaques. Since HD vectors have been show to have an increased safety profile, do not possess any Ad genes, can be packaged by multiple serotype helper viruses, and elicit strong anti-HIV immune responses, they warrant further investigation as alternatives to FG vectors as gene-based vaccines.