In the enterobacterial species Escherichia coli and Salmonella enterica, expression of horizontally acquired genes with a higher than average AT content is repressed by the nucleoid-associated protein H-NS. A classical example of an H-NS-repressed locus is the bgl (aryl-beta,D-glucoside) operon of E. coli. This locus is "cryptic," as no laboratory growth conditions are known to relieve repression of bgl by H-NS in E. coli K12. However, repression can be relieved by spontaneous mutations. Here, we investigated the phylogeny of the bgl operon. Typing of bgl in a representative collection of E. coli demonstrated that it evolved clonally and that it is present in strains of the phylogenetic groups A, B1, and B2, while it is presumably replaced by a cluster of ORFans in the phylogenetic group D. Interestingly, the bgl operon is mutated in 20% of the strains of phylogenetic groups A and B1, suggesting erosion of bgl in these groups. However, bgl is functional in almost all B2 isolates and, in approximately 50% of them, it is weakly expressed at laboratory growth conditions. Homologs of bgl genes exist in Klebsiella, Enterobacter, and Erwinia species and also in low GC-content Gram-positive bacteria, while absent in E. albertii and Salmonella sp. This suggests horizontal transfer of bgl genes to an ancestral Enterobacterium. Conservation and weak expression of bgl in isolates of phylogenetic group B2 may indicate a functional role of bgl in extraintestinal pathogenic E. coli.