More than 30 years after the first report of successful vaccination against malaria using radiation-attenuated sporozoites, an effective malaria vaccine is not yet available. However, field and experimental data indicate that it can be developed. An astonishing amount of data has accumulated concerning parasite biology, host-parasite interactions, immunity and escape mechanisms, targets and modulators of immune responses. Nevertheless, so far this knowledge has not been enough to make us understand how to properly manipulate the whole system to build an effective vaccine. In this article, we describe candidate antigens, mechanisms, targets and trials performed with potential malaria vaccines and discuss the approaches, in vivo and in vitro models, constraints and how technologies such as DNA vaccination, genomics/proteomics and reverse immunogenetics are providing exciting results and opening new doors to make malaria vaccine a reality.