The trypanosome alternative oxidase (TAO), a mitochondrial enzyme involved in the respiration of the bloodstream form trypomastigotes of <i>Trypanosoma brucei</i>, is a validated drug target against African trypanosomes. Earlier series of TAO inhibitors having a 2,4-dihydroxy-6-methylbenzoic acid scaffold ("head") and a triphenylphosphonium or quinolin-1-ium cation as a mitochondrion-targeting group ("tail") were shown to be nanomolar inhibitors in enzymatic and cellular assays. We investigated here the effect of different mitochondrion-targeting cations and other scaffold modifications on the in vitro activity of this class of inhibitors. Low micromolar range activities were obtained, and the structure-activity relationship studies showed that modulation of the tail region with polar substituents is generally detrimental to the enzymatic and cellular activity of TAO inhibitors.