Amino acid hydroxylation is a post-translational modification that 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. Using quantitative interaction proteomics, we screened for substrates of the proline hydroxylase PHD3 and the asparagine hydroxylase FIH, which regulate the HIF-mediated hypoxic response. We were able to identify hundreds of potential substrates. Enrichment analysis revealed that the potential substrates of both hydroxylases cluster in the same pathways but frequently modify different nodes of signaling networks. We confirm that two proteins identified in our screen, MAPK6 (Erk3) and RIPK4, are indeed hydroxylated in a FIH- or PHD3-dependent mechanism. We further determined that FIH-dependent hydroxylation regulates RIPK4-dependent Wnt signaling, and that PHD3-dependent hydroxylation of MAPK6 protects the protein from proteasomal degradation.