Lipopolysaccharide (LPS) is the major component of the surface of Gram-negative bacteria and its polysaccharide portion is situated at the outermost region. We investigated the relationship between the polysaccharide portion of LPS and biofilm formation using a series of Escherichia coli mutants defective in genes earlier shown to affect the LPS sugar compositions. Biofilm formation by a deep rough LPS mutant, the hldE strain, was strongly enhanced in comparison with the parental strain and other LPS mutants. The hldE strain also showed a phenotype of increased auto-aggregation and stronger cell surface hydrophobicity compared to the wild-type. Similar results were obtained with another deep rough LPS mutant, the waaC strain whose LPS showed same molecular mass as that of the hldE strain. Confocal laser scanning microscopy (CLSM) analysis and biofilm formation assay using DNase I revealed that biofilm formation by the hldE strain was dependent on extracellular DNA. Furthermore, a loss of flagella and an increase in amount of outer membrane vesicles in case of the hldE strain were also observed by transmission electron microscopy and atomic force microscopy, respectively. In addition, we demonstrated that a mutation in the hldE locus, which alters the LPS structure, caused changes in both expression and properties of several surface bacterial factors involved in biofilm formation and virulence. We suggest that the implication of these results should be considered in the context of biofilm formation on abiotic surfaces, which is frequently associated with nosocominal infections such as the catheter-associated infections.