Type 5 human adenoviruses (Ad5) deleted of genes encoding the early region 1B 55-kDa (E1B55K) protein including Onyx-015 (dl1520) and H101 are best known for their oncolytic potential. As a vaccine vector the E1B55K deletion may allow for the insertion of a transgene nearly 1,000 base pairs larger than now possible. This has the potential of extending the application for which the vectors are clinically known. However, the immune priming ability of E1B55K-deleted vectors is unknown, undermining our ability to gauge their usefulness in vaccine applications. For this reason, we created an E1B55K-deleted Ad5 vector expressing full-length single chain HIVBaLgp120 attached to a flexible linker and the first two domains of rhesus CD4 (rhFLSC) in exchange for the E3 region. In cell-based experiments the E1B55K-deleted vector promoted higher levels of innate immune signals including chemokines, cytokines, and the NKG2D ligands MIC A/B compared to an E1B55K wild-type vector expressing the same immunogen. Based on these results we evaluated the immune priming ability of the E1B55K-deleted vector in mice. The E1B55K-deleted vector promoted similar levels of Ad5-, HIVgp120, and rhFLSC-specific cellular and humoral immune responses as the E1B55K wild-type vector. In pre-clinical HIV-vaccine studies the wild-type vector has been employed as part of a very effective prime-boost strategy. This study demonstrates that E1B55K-deleted adenoviruses may serve as effective vaccine delivery vectors.