Background: Malaria greatly impacts the health and wellbeing of over half of the world's population. Promising malaria vaccine candidates have attempted to induce adaptive immune responses to Circumsporozoite (CS) protein. Despite the inclusion of potent adjuvants, these vaccines have limited protective efficacy. Conventional recombinant adenovirus (rAd) based vaccines expressing CS protein can induce CS protein specific immune responses, but these are essentially equivalent to those generated after use of the CS protein subunit based vaccines. In this study we combined the use of rAds expressing CS protein along with rAds expressing novel innate immune response modulating proteins in an attempt to significantly improve the induction of CS protein specific cell mediated immune (CMI) responses. Methods and Findings: BALB/cJ mice were co-vaccinated with a rAd vectors expressing CS protein simultaneous with a rAd expressing either TLR agonist (rEA) or SLAM receptors adaptor protein (EAT-2). Paradoxically, expression of the TLR agonist uncovered a potent immunosuppressive activity inherent to the combined expression of the CS protein and rEA. Fortunately, use of the rAd vaccine expressing EAT-2 circumvented CS protein's suppressive activity, and generated a fivefold increase in the number of CS protein responsive, IFNγ secreting splenocytes, as well as increased the breadth of T cells responsive to peptides present in the CS protein. These improvements were positively correlated with the induction of a fourfold improvement in CS protein specific CTL functional activity in vivo. Conclusion: Our results emphasize the need for caution when incorporating CS protein into malaria vaccine platforms expressing or containing other immunostimulatory compounds, as the immunological outcomes may be unanticipated and/or counter-productive. However, expressing the SLAM receptors derived signaling adaptor EAT-2 at the same time of vaccination with CS protein can overcome these concerns, as well as significantly improve the induction of malaria antigen specific adaptive immune responses in vivo.