DNA methylation damage can be induced by endogenous and exogenous chemical agents, which has led every living organism to develop suitable response strategies. We investigated protein expression profiles of Escherichia coli upon exposure to the alkylating agent methyl-methane sulfonate (MMS) by differential proteomics. Quantitative proteomic data showed a massive downregulation of enzymes belonging to the glycolytic pathway and fatty acids degradation, strongly suggesting a decrease of energy production. A strong reduction in the expression of the N-acetylneuraminate lyases (NanA) involved in the sialic acid metabolism was also observed. Using a null NanA mutant and DANA, a substrate analogue acting as competitive inhibitor, we demonstrated that down regulation of NanA affects biofilm formation and adhesion properties of E. coli MV1161. Exposure to alkylating agents also decreased biofilm formation and bacterial adhesion to Caco-2 eukaryotic cell line by the adherent invasive E. coli (AIEC) strain LF82. Our data showed that methylation stress impairs E. coli adhesion properties and suggest a possible role of NanA in biofilm formation and bacteria host interactions.