BACKGROUND: Adenoviral based vectors remain promising vaccine platforms for use against numerous pathogens, including HIV. Recent vaccine trials utilizing Adenovirus based vaccines expressing HIV antigens confirmed induction of cellular immune responses, but these responses failed to prevent HIV infections in vaccinees. This illustrates the need to develop vaccine formulations capable of generating more potent T-cell responses to HIV antigens, such as HIV-Gag, since robust immune responses to this antigen correlate with improved outcomes in long-term non-progressor HIV infected individuals. METHODOLOGY/PRINCIPAL FINDINGS: In this study we designed a novel vaccine strategy utilizing an Ad-based vector expressing a potent TLR agonist derived from Eimeria tenella as an adjuvant to improve immune responses from a [E1-]Ad-based HIV-Gag vaccine. Our results confirm that expression of rEA elicits significantly increased TLR mediated innate immune responses as measured by the influx of plasma cytokines and chemokines, and activation of innate immune responding cells. Furthermore, our data show that the quantity and quality of HIV-Gag specific CD8(+) and CD8(-) T-cell responses were significantly improved when coupled with rEA expression. These responses also correlated with a significantly increased number of HIV-Gag derived epitopes being recognized by host T cells. Finally, functional assays confirmed that rEA expression significantly improved antigen specific CTL responses, in vivo. Moreover, we show that these improved responses were dependent upon improved TLR pathway interactions. CONCLUSION/SIGNIFICANCE: The data presented in this study illustrate the potential utility of Ad-based vectors expressing TLR agonists to improve clinical outcomes dependent upon induction of robust, antigen specific immune responses.