Protein phosphorylation on serine, threonine and tyrosine (Ser/Thr/Tyr) is generally considered the major regulatory posttranslational modification (PTM) 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 mass spectrometry 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 on 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 non-phosphorylated counterparts, with a number of potential phosphorylation sites conserved from Archaea to humans. Our results establish Ser/Thr/Tyr phosphorylation as a common PTM in Eubacteria, present since the onset of cellular life.