The trypanosomatid parasites Leishmania and Trypanosoma are responsible for the most important WHO-designated neglected tropical diseases, for which the need for cost-effective new drugs is urgent. In addition to the classical eukaryotic 20S and 26S proteasomes, these unconventional eukaryotes possess a bacterial-like protease complex, HslVU, made of proteolytic (HslV) and regulatory (HslU) subunits. In trypanosomatids, two paralogous genes are co-expressed: HslU1 and HslU2. Conflicting reports have been published with respect to subcellular localization, functional redundancy and putative roles of the different subunits of this complex in trypanosomatids. Here, we definitively established the mitochondrial localization of HslVU in L. major procyclic promastigotes and of HslV in T. brucei bloodstream trypomastigotes, the latter being the form responsible for the disease in the mammalian host. Moreover, our data demonstrate for the first time the essential nature of HslVU in the bloodstream trypomastigotes of T. brucei, in spite of mitochondrial repression at this stage. Interestingly, our work also allows distinguishing a specific role for the different members of the complex, as HslV and HslU1 appear to be involved in the control of different cell cycle events. Finally, these data validate HslVU as a promising drug target against these parasitic diseases of wide medical and economical importance.