Vaccines against many diseases caused by complex pathogens are still not available despite intense research. The genome, proteome and transcriptome of a number of these challenging pathogens have been now elucidated, and provide the foundation for systematic genome-based approaches to identify target antigens for rational vaccine design. Using malaria as a model complex pathogen, we have developed and applied a strategy using T cell epitope prediction algorithms in reverse to identify and prioritize from the complete Plasmodium falciparum parasite proteome the subset of key antigens targeted by T cell responses from individuals with clinical immunity to malaria. We have also pursued proteome-wide screening using protein microarrays and sera from malaria-immune individuals to identify antigens targeted by antibody responses. Integrating our proteome-wide datasets showed that antigens preferentially recognized by T cells are distinct from antibody targets, suggesting that different vaccine approaches and antigen targets are required depending on whether antibodies or T cells are the desired vaccination outcome. Specific genomic, structural or physiochemical attributes could distinguish T cell versus antibody targets, facilitating the development of a predictive algorithm for immune class. Fourteen of the most highly ranked P. falciparum T cell antigens were evaluated for immunogenicity and capacity to protect against stringent cross-species P. yoelii parasite challenge in mice. Three immunization regimens were explored: homologous DNA-DNA, heterologous DNA-Adenovirus, and an innovative prime-target regimen designed to induce sustained T cell responses in the liver. Many of our novel P. falciparum antigens were effective targets of cross-species protective immunity, as evidenced by sterile infection-blocking immunity, reduction in liver-stage and blood-stage parasite burden or delay to onset of parasitemia. We have down-selected for clinical development a subset of antigens with maximum likelihood of inducing strain-transcending and cross-species protective immunity against malaria in humans. Such a rationally-designed genome-based vaccine would be expected to protect against all strains and all species of malaria.