Drosophila tracheal terminal branches are plastic and have the capacity to sprout out projections toward oxygen-starved areas, in a process analogous to mammalian angiogenesis. This response involves the upregulation of FGF/Branchless in hypoxic tissues, which binds its receptor Breathless on tracheal cells. Here, we show that extra sprouting depends on the Hypoxia-Inducible Factor (HIF)-α homolog Sima and on the HIF-prolyl hydroxylase Fatiga that operates as an oxygen sensor. In mild hypoxia, Sima accumulates in tracheal cells, where it induces breathless, and this induction is sufficient to provoke tracheal extra sprouting. In nontracheal cells, Sima contributes to branchless induction, whereas overexpression of Sima fails to attract terminal branch outgrowth, suggesting that HIF-independent components are also required for full induction of the ligand. We propose that the autonomous response to hypoxia that occurs in tracheal cells enhances tracheal sensitivity to increasing Branchless levels, and that this mechanism is a cardinal step in hypoxia-dependent tracheal sprouting.