Previously, we have shown the potency of recombinant Adenovirus serotype 35 viral vaccines (rAd35) to induce strong immune response against the circumsporozoite protein (CS) of the plasmodium parasite. To further optimize immunogenicity of Ad35-based malaria vaccines we formulated rAd35.CS vaccine with aluminium phosphate adjuvant (AlPO(4)). In contrast to the conventional protein based vaccines no absorption to aluminium adjuvant was observed and rAd35 viral in vitro infectivity in mammalian cells was preserved. Immunization with Ad35.CS formulated with AlPO(4) resulted in significantly higher CS specific T and B cell responses in mice upon either single or prime-boost vaccination regimens as compared to rAd35.CS alone. With these results we report for the first time the feasibility of using an AlPO(4) adjuvant to increase the potency of a live adenovirus serotype 35-based vaccine.