The composition of the lipo-oligosaccharide (LOS) of Haemophilus influenzae is highly variable, especially in the oligosaccharide region. Many of the biosynthetic and transferase genes involved in LOS biosynthesis vary in seemingly random fashion by means of polymerase stuttering within redundant sequences in the 5'-portion of the genes. This results in a heterogeneous population of individual bacteria expressing literally thousands of LOS glycoforms. The simultaneous variation in the expression and structural context of a large number of individual carbohydrate and lipid structures within the LOS yields a diverse array of LOS glycoforms. The expression of glycoforms that mimic host structures may allow the organism to evade innate defenses and to manipulate host cell biology. We review how this randomly generated bacterial combinatorial chemistry results in the production of a large number of carbohydrate structures, in essentially any conceivable structural context, some of which allow the organism to utilize host cell receptors. By generating a diverse population of bacteria expressing different LOS glycoforms, discrete H. influenzae subpopulations may be adapted for survival of different environmental stresses within the airways. Thus, H. influenzae utilizes a simple and efficient "Monte Carlo" strategy for achieving maximal variation in cell surface structures, which allow the organism to adapt efficiently to environmental stresses with a small genome.