Amino acid hydroxylation is a common post-translational modification which regulates intra and inter-molecular protein-protein interactions. The modifications are regulated by a family of 2-oxoglutarate (2OG) dependent enzymes and although the biochemistry is well understood, until now only a few substrates have been described for these enzymes. We present here a sensitive method which specifically enriches and identifies hydroxylase substrates. We screened for substrates of PHD3 and FIH, a proline and asparagine hydroxylase respectively which regulate the HIF-mediated hypoxic response and were able to confirm known substrates as well as identifying hundreds of potential novel ones. Enrichment analysis revealed that the substrates of both hydroxylases cluster in the same pathways but frequently modify different nodes of these networks. We confirm that two proteins identified in this screen, MAPK6 and RIPK4, are indeed hydroxylated in a FIH or PHD3 dependent mechanism and explore the biological consequences of the hydroxylation.