The concept of a malaria vaccine has sparked great interest for decades; however, the challenge is proving to be a difficult one. Immune dysregulation by Plasmodium and the ability of the parasite to mutate critical epitopes in surface antigens have proved to be strong defense weapons. This has led to reconsideration of polyvalent and whole parasite strategies and ways to enhance cellular immunity to malaria that may be more likely to target conserved antigens and an expanded repertoire of antigens. These and other concepts will be discussed in this review.