Burkholderia cenocepacia H111, a strain isolated from a cystic fibrosis patient, has been shown to effectively kill the nematode Caenorhabditis elegans. We used the C. elegans model of infection to screen a mini-Tn5 mutant library of B. cenocepacia H111 for attenuated virulence. Of the approximately 5,500 B. cenocepacia H111 random mini-Tn5 insertion mutants that were screened, 22 showed attenuated virulence in C. elegans. Except for the quorum-sensing regulator cepR, none of the mutated genes coded for the biosynthesis of classical virulence factors such as extracellular proteases or siderophores. Instead, the mutants contained insertions in metabolic and regulatory genes. Mutants attenuated in virulence in the C. elegans infection model were also tested in the Drosophila melanogaster pricking model, and those also attenuated in this model were further tested in Galleria mellonella. Six of the 22 mutants were attenuated in D. melanogaster, and five of these were less pathogenic in the G. mellonella model. We show that genes encoding enzymes of the purine, pyrimidine, and shikimate biosynthesis pathways are critical for virulence in multiple host models of infection.