Flocculation has been recognized for hundreds of years as an important phenomenon in brewing and wastewater treatment. However, the underlying molecular mechanisms remain elusive. The lack of a distinct phenotype to differentiate between slow-growing mutants and floc-forming mutants prevents the isolation of floc-related gene by conventional mutant screening. To overcome this, we performed a two-step Escherichia coli mutant screen. The initial screen of E. coli for mutants conferring floc production during high salt treatment yielded a mutant containing point mutations in 61 genes. The following screen of the corresponding single-gene mutants identified two genes, mrcB, encoding a peptidoglycan-synthesizing enzyme and cpxA, encoding a histidine kinase of a two-component signal transduction system that contributed to salt tolerance and flocculation prevention. Both single mutants formed flocs during high salt shock, these flocs contained cytosolic proteins. ΔcpxA exhibited decreased growth with increasing floc production and addition of magnesium to ΔcpxA suppressed floc production effectively. In contrast, the growth of ΔmrcB was inconsistent under high salt conditions. In both strains, flocculation was accompanied by the release of membrane vesicles containing inner and outer membrane proteins. Of 25 histidine kinase mutants tested, ΔcpxA produced the highest amount of proteins in floc. Expression of cpxP was up-regulated by high salt in ΔcpxA, suggesting that high salinity and activation of CpxR might promote floc formation. The finding that ΔmrcB or ΔcpxA conferred floc production indicates that cell envelope stress triggered by unfavorable environmental conditions cause the initiation of flocculation in E. coli.