Protein hydroxylation extensively regulates cellular signaling by affecting protein stability, protein-protein interaction and protein activity, and its dysregulation contributes to the pathogenesis of various diseases including cancers. However, because of the transient nature of the enzyme-substrate interaction, identifying new prolyl hydroxylation substrates remains a daunting challenge. Here, by developing a novel substrate-trapping strategy combining tumor hypoxia and hydroxylase pharmacological inhibition with TAP-TAG purification followed by mass spectrometry, we identify ADSL as a bona fide EglN2 prolyl hydroxylase substrate in triple negative breast cancer (TNBC). ADSL expression is significantly higher in TNBC than in the other breast cancer subtypes and normal breast tissues. Functionally, ADSL knock out greatly impairs TNBC 2-D and 3-D cell proliferation and invasiveness in vitro, as well as TNBC tumorigenesis and metastasis in xenograft models. Mechanistically, the integrated transcriptome and metabolome analysis reveals that ADSL promotes the activation of the oncogene cMYC pathway by regulating cMYC protein level via a mechanism requiring ADSL hydroxylation. Specifically, ADSL, by affecting adenosine levels, controls the expression of the long non-coding RNA MIR22HG, which negatively regulates the oncogene cMYC protein level and, thus, cMYC target gene expression. Our findings identify ADSL and ADSL hydroxylation as potential therapeutic targets in TNBC.