In the past 25 years, the development of an effective malaria vaccine has become one of the biggest riddles in the biomedical sciences. Experimental data using animal infection models demonstrated that it is possible to induce protective immunity against different stages of malaria parasites. Nonetheless, the vast body of knowledge has generated disappointments when submitted to clinical conditions and presently a single antigen formulation has progressed to the point where it may be translated into a human vaccine. In parallel, new means to increase the protective effects of antigens in general have been pursued and depicted, such as the use of bacterial flagellins as carriers/adjuvants. Flagellins activate pathways in the innate immune system of both mice and humans. The recent report of the first Phase I clinical trial of a vaccine containing a Salmonella flagellin as carrier/adjuvant may fuel the use of these proteins in vaccine formulations. Herein, we review the studies on the use of recombinant flagellins as vaccine adjuvants with malarial antigens in the light of the current state of the art of malaria vaccine development. The available information indicates that bacterial flagellins should be seriously considered for malaria vaccine formulations to the development of effective human vaccines.