Burkholderia pseudomallei is a Gram-negative bacterium which is the causative agent of melioidosis, a disease which carries a high mortality and morbidity rate in endemic areas of South East Asia and Northern Australia. At present there is no available human vaccine that protects against B. pseudomallei, and with the current limitations of antibiotic treatment, the development of new preventative and therapeutic interventions is crucial. This review considers the multiple elements of melioidosis vaccine research including: (i) the immune responses required for protective immunity, (ii) animal models available for preclinical testing of potential candidates, (iii) the different experimental vaccine strategies which are being pursued, and (iv) the obstacles and opportunities for eventual registration of a licensed vaccine in humans.