Cells adapt to hypoxia by a cellular response, where hypoxia-inducible factor 1α (HIF-1α) becomes stabilized and directly activates transcription of downstream genes. In addition to this “canonical” response, certain aspects of the pathway require integration with Notch signaling, i.e., HIF-1α can interact with the Notch intracellular domain (ICD) to augment the Notch downstream response. In this work, we demonstrate an additional level of complexity in this cross-talk: factor-inhibiting HIF-1 (FIH-1) regulates not only HIF activity, but also the Notch signaling output and, in addition, plays a role in how Notch signaling modulates the hypoxic response. We show that FIH-1 hydroxylates Notch ICD at two residues (N¹⁹⁴⁵ and N²⁰¹²) that are critical for the function of Notch ICD as a transactivator within cells and during neurogenesis and myogenesis in vivo. FIH-1 negatively regulates Notch activity and accelerates myogenic differentiation. In its modulation of the hypoxic response, Notch ICD enhances recruitment of HIF-1α to its target promoters and derepresses HIF-1α function. Addition of FIH-1, which has a higher affinity for Notch ICD than for HIF-1α, abrogates the derepression, suggesting that Notch ICD sequesters FIH-1 away from HIF-1α. In conclusion, the data reveal posttranslational modification of the activated form of the Notch receptor and an intricate mode of cross-coupling between the Notch and hypoxia signaling pathways.