Adenovirus (Ad) is still under extensive investigation as a vector for HIV vaccination; however, one possible explanation for the failure of Merck's STEP trial is the relatively weak immunogenicity of replication-defective Ad vectors. In this study, a novel strategy to enhance the immunogenicity of replication-defective Ad-based HIV vaccines was developed. First, a recombinant plasmid expressing adenoviral E1 protein (pVAX-E1) was constructed to complement the E1-deleted replication-defective Ad vectors in trans. Then, the immunogenicity of the vaccine regimen of Ad5-HIV gag plus pVAX-E1 plasmid was assessed in rhesus macaques. Compared with traditional administration of Ad-based vectors alone, the results showed that our strategy elicited a more sustained and robust HIV gag-specific cellular response and enhanced long-term proliferation of CD4(+) and CD8(+) T lymphocytes. This strategy represents a proof-of-concept that enhances the immunogenicity of replication-defective Ad-based vectors, and it exemplifies the useful implications for Ad-based HIV vaccines and other vaccines.