ATP-dependent protease complexes are present in all living organisms, including the 26S proteasome in eukaryotes, Archaea, and Actinomycetales, and the HslVU protease in eubacteria. The structure of HslVU protease resembles that of the 26S proteasome, and the simultaneous presence of both proteases in one organism was deemed unlikely. However, HslVU homologs have been identified recently in some primordial eukaryotes, though their potential function remains elusive. We characterized the HslVU homolog from Trypanosoma brucei, a eukaryotic protozoan parasite and the causative agent of human sleeping sickness. TbHslVU has ATP-dependent peptidase activity and, like its bacterial counterpart, has essential lysine and N-terminal threonines in the catalytic subunit. By epitope tagging, TbHslVU localizes to mitochondria and is associated with the mitochondrial genome, kinetoplast DNA (kDNA). RNAi of TbHslVU dramatically affects the kDNA by causing over-replication of the minicircle DNA. This leads to defects in kDNA segregation and, subsequently, to continuous network growth to an enormous size. Multiple discrete foci of nicked/gapped minicircles are formed on the periphery of kDNA disc, suggesting a failure in repairing the gaps in the minicircles for kDNA segregation. TbHslVU is a eubacterial protease identified in the mitochondria of a eukaryote. It has a novel function in regulating mitochondrial DNA replication that has never been observed in other organisms. © 2008 Li et al.