African trypanosomiasis is a neglected parasitic disease that is still of great public health relevance, and a severe impediment to agriculture in endemic areas. The pathogens possess certain unique metabolic features that can be exploited for the development of new drugs. Notably, they rely on an essential, mitochondrially-localized enzyme, Trypanosome Alternative Oxidase (TAO) for their energy metabolism, which is absent in the mammalian hosts and therefore an attractive target for the design of safe drugs. In this study, we cloned, expressed and purified the physiologically relevant form of TAO, which lacks the N-terminal 25 amino acid mitochondrial targeting sequence (ΔMTS-TAO). A new class of 32 cationic and non-cationic 4-hydroxybenzoate and 4-alkoxybenzaldehyde inhibitors was designed and synthesized, enabling the first structure-activity relationship studies on ΔMTS-TAO. Remarkably, we obtained compounds with enzyme inhibition values (IC50) as low as 2 nM, which were efficacious against wild type and multidrug-resistant strains of T. brucei and T. congolense. The inhibitors 13, 15, 16, 19, and 30, designed with a mitochondrion-targeting lipophilic cation tail, displayed trypanocidal potencies comparable to the reference drugs pentamidine and diminazene, and showed no cross-resistance with the critical diamidine and melaminophenyl arsenical classes of trypanocides. The cationic inhibitors 15, 16, 19, 20, and 30 were also much more selective (900 - 344,000) over human cells than the non-targeted neutral derivatives (selectivity >8-fold). A preliminary in vivo study showed that modest doses of 15 and 16 reduced parasitaemia of mice infected with T. b. rhodesiense (STIB900). These compounds represent a promising new class of potent and selective hits against African trypanosomes.