The single-celled parasite Trypanosoma brucei causes sleeping sickness in humans and nagana in livestock and is transmitted by hematophagous tsetse flies. Lifecycle progression from mammalian bloodstream form to tsetse midgut form and, subsequently, infective salivary gland form depends on complex developmental steps and migration within different fly tissues. As the parasite colonises the glucose-poor insect midgut, its ATP production is thought to depend on activation of mitochondrial amino acid catabolism via oxidative phosphorylation. This process involves respiratory chain complexes and the F1FO-ATP synthase, and it requires protein subunits of these complexes that are encoded in the parasite’s mitochondrial DNA (kinetoplast or kDNA). Here we show that a progressive loss of kDNA-encoded functions correlates with an increasingly impaired ability of T. brucei to initiate and complete its development in the tsetse. First, parasites with a mutated F1FO-ATP synthase with a reduced capacity for oxidative phosphorylation can initiate differentiation from bloodstream to insect form, but they are unable to proliferate in vitro. Unexpectedly, these cells can still colonise the tsetse midgut. However, these parasites exhibit a motility defect and are severely impaired in colonising or migrating to subsequent tsetse tissues. Second, parasites with a fully disrupted F1FO-ATP synthase complex that is completely unable to produce ATP by oxidative phosphorylation can still differentiate to the first insect stage in vitro but die within a few days and cannot establish a midgut infection in vivo. Third, mutant parasites lacking kDNA entirely can initiate differentiation but die within 24 h. Together, these three scenarios show that efficient ATP production via oxidative phosphorylation is not essential for initial colonisation of the tsetse vector, but it is required to power trypanosome migration within the fly.