Protein-in-adjuvant vaccines have shown limited success against difficult diseases such as blood-stage malaria. Here we show that a recombinant adenovirus-poxvirus prime-boost immunization regime (known to induce strong T cell immunogenicity) can also induce very strong antigen-specific antibody responses, and we identify a simple complement-based adjuvant to further enhance immunogenicity. Antibodies induced against a blood-stage malaria antigen by this viral vector platform are highly effective against Plasmodium yoelii parasites in mice and against Plasmodium falciparum in vitro.