Protein phosphorylation on serine, threonine, and tyrosine (Ser/Thr/Tyr) is generally considered the major regulatory posttranslational modification in eukaryotic cells. Increasing evidence at the genome and proteome level shows that this modification is also present and functional in prokaryotes. We have recently reported the first in-depth phosphorylation site-resolved dataset from the model Gram-positive bacterium, Bacillus subtilis, showing that Ser/Thr/Tyr phosphorylation is also present on many essential bacterial proteins. To test whether this modification is common in Eubacteria, here we use a recently developed proteomics approach based on phosphopeptide enrichment and high accuracy MS to analyze the phosphoproteome of the model Gram-negative bacterium Escherichia coli. We report 81 phosphorylation sites on 79 E. coli proteins, with distribution of Ser/Thr/Tyr phosphorylation sites 68%/23%/9%. Despite their phylogenetic distance, phosphoproteomes of E. coli and B. subtilis show striking similarity in size, classes of phosphorylated proteins, and distribution of Ser/Thr/Tyr phosphorylation sites. By combining the two datasets, we created the largest phosphorylation site-resolved database of bacterial phosphoproteins to date (available at www.phosida.com) and used it to study evolutionary conservation of bacterial phosphoproteins and phosphorylation sites across the phylogenetic tree. We demonstrate that bacterial phosphoproteins and phosphorylated residues are significantly more conserved than their nonphosphorylated counterparts, with a number of potential phosphorylation sites conserved from Archaea to humans. Our results establish Ser/Thr/Tyr phosphorylation as a common posttranslational modification in Eubacteria, present since the onset of cellular life.