Protein hydroxylation at proline and lysine residues is known to have important effects on cellular functions, such as the response to hypoxia. However, protein hydroxylation at tyrosine residues (called protein-bound 3,4-dihydroxy-phenylalanine (PB-DOPA)) has not been carefully examined. Here we report the first proteomics screening of the PB-DOPA protein substrates and their sites in Escherichia coli and human mitochondria by nano-liquid chromatography/tandem mass spectrometry (nano-LC/MS/MS) and protein sequence alignment using the PTMap algorithm. Our study identified 67 novel PB-DOPA sites in 43 E. coli proteins and 9 novel PB-DOPA sites in 7 proteins from HeLa mitochondria. Bioinformatics analysis indicates that the structured region is more favored than the unstructured regions of proteins for the PB-DOPA modification. The PB-DOPA substrates in E. coli were dominantly enriched in proteins associated with carbohydrate metabolism. Our study showed that PB-DOPA may be involved in regulation of the specific activity of certain evolutionarily conserved proteins such as superoxide dismutase and glyceraldehyde 3-phosphate dehydrogenase, suggesting the conserved nature of the modification among distant biological species. The substrate proteins identified in this study offer a rich source for determining their regulatory enzymes and for further characterization of the possible contributions of this modification to cellular physiology and human diseases.