The O-polysaccharide (O-antigen) of Salmonella enterica O51 was isolated by mild acid degradation of the lipopolysaccharide and its structure was established using sugar analysis and NMR spectroscopy. The O-antigen of Escherichia coli O23, whose structure was elucidated earlier, possesses a similar structure and differs only in the presence of an additional lateral α-D-Glcp residue at position 6 of the GlcNAc residue in the main chain. Sequencing of the O-antigen gene clusters of S. enterica O51 and E. coli O23 revealed the same genes with a high-level similarity. By comparison with opened gene databases, all genes expected for the synthesis of the common structure of the two O-antigens were assigned functions. It is suggested that the gene clusters of both bacteria originated from a common ancestor, whereas the O-antigen modification in E. coli O23, which, most probably, is induced by prophage genes outside the gene cluster, could be introduced after the species divergence.