Lipopolysaccharide (LPS) is one of the most important virulence and antigenic components of Burkholderia pseudomallei, the causative agent of melioidosis. LPS diversity in B. pseudomallei has been described as typical, atypical or rough, based upon banding patterns on SDS-PAGE. Here, we studied the genetic and molecular basis of these phenotypic differences. Bioinformatics was used to determine the diversity of genes known or predicted to be involved in biosynthesis of the O-antigenic moiety of LPS in B. pseudomallei and its near-relative species. Multiplex-PCR assays were developed to target diversity of the O-antigen biosynthesis gene patterns or LPS genotypes in B. pseudomallei populations. We found that the typical LPS genotype (LPS genotype A) was highly prevalent in strains from Thailand and other countries in Southeast Asia, whereas the atypical LPS genotype (LPS genotype B) was most often detected in Australian strains (~13.8%). In addition, we report a novel LPS ladder pattern, a derivative of the atypical LPS phenotype, associated with an uncommon O-antigen biosynthesis gene cluster that is found in only a small B. pseudomallei sub-population. This new LPS group was designated as genotype B2. We also report natural mutations in the O-antigen biosynthesis genes that potentially cause the rough LPS phenotype. We postulate that the diversity of LPS may correlate with differential immunopathogenicity and virulence among B. pseudomallei strains.