Burkholderia are highly evolved Gram-negative bacteria that primarily infect solipeds but are transmitted to humans by ingestion and cutaneous or aerosol exposures. Heightened concern over human infections of Burkholderia mallei and the very closely related species B. pseudomallei is due to the pathogens’ proven effectiveness as bioweapons, and to the increased potential for natural opportunistic infections in the growing diabetic and immuno-compromised populations. These Burkholderia species are nearly impervious to antibiotic treatments and no vaccine exists. In this study, the genome of the highly virulent B. mallei ATCC23344 strain was examined by expression library immunization for gene-encoded protective antigens. This protocol for genomic-scale functional screening was customized to accommodate the unusually large complexity of Burkholderia, and yielded 12 new putative vaccine candidates. Five of the candidates were individually tested as protein immunogens and three were found to confer significant partial protection against a lethal pulmonary infection in a murine model of disease. Determinations of peripheral blood cytokine and chemokine profiles following individual protein immunizations show that interleukin-2 (IL-2) and IL-4 are elicited by the three confirmed candidates, but unexpectedly interferon-γ and tumor necrosis factor-α are not. We suggest that these pathogen components, discovered using genetic immunization and confirmed in a conventional protein format, will be useful toward the development of a safe and effective glanders vaccine.