Replication-defective adenovirus vectors, primarily developed from serotype 5 (Ad5) viruses, have been widely used for gene transfer and vaccination approaches. Vectors based on other serotypes of adenovirus could be used in conjunction with, or in place of, Ad5 vectors. In this study, Ad41, an enteric adenovirus usually described as 'non-cultivable' or 'fastidious,' has been successfully cloned, rescued and propagated on 293-ORF6 cells. The complementation capabilities of this cell line allow generation of Ad41 vectors at titers comparable to those obtained for Ad5 vectors. Mice immunized with an Ad41 vector containing an HIV envelope (Env) gene mounted anti-Env cellular and humoral immune responses. Ad41-Env vectors appear to be particularly attractive when used in heterologous prime-boost regimens, where they induce significantly higher cellular immune responses to HIV-Env than Ad5-based regimens. Ad41-based constructs are attractive vaccine vectors alone or in combination with Ad5 adenovectors, since each vector type can provide circumvention of pre-existing immunity to the other.