A Burkholderia cenocepacia infection usually leads to reduced survival and fatal cepacia syndrome in cystic fibrosis patients. The identification of B. cenocepacia essential genes for in vivo survival is key to designing new anti-infectives therapies. We used the Transposon-Directed Insertion Sequencing (TraDIS) approach to identify genes required for B. cenocepacia survival in the model infection host, Caenorhabditis elegans. A B. cenocepacia J2315 transposon pool of ∼500,000 mutants was used to infect C. elegans. We identified 178 genes as crucial for B. cenocepacia survival in the infected nematode. The majority of these genes code for proteins of unknown function, many of which are encoded by the genomic island BcenGI13, while other gene products are involved in nutrient acquisition, general stress responses and LPS O-antigen biosynthesis. Deletion of the glycosyltransferase gene wbxB and a histone-like nucleoid structuring (H-NS) protein-encoding gene (BCAL0154) reduced bacterial accumulation and attenuated virulence in C. elegans. Further analysis using quantitative RT-PCR indicated that BCAL0154 modulates B. cenocepacia pathogenesis via transcriptional regulation of motility-associated genes including fliC, fliG, flhD, and cheB1. This screen has successfully identified genes required for B. cenocepacia survival within the host-associated environment, many of which are potential targets for developing new antimicrobials.