Mitochondria cannot form de novo but require mechanisms that mediate their inheritance to daughter cells. The parasitic protozoan Trypanosoma brucei has a single mitochondrion with a single-unit genome that is physically connected across the two mitochondrial membranes with the basal body of the flagellum. This connection, termed the tripartite attachment complex (TAC), is essential for the segregation of the replicated mitochondrial genomes prior to cytokinesis. Here we identify a protein complex consisting of three integral mitochondrial outer membrane proteins-TAC60, TAC42 and TAC40-which are essential subunits of the TAC. TAC60 contains separable mitochondrial import and TAC-sorting signals and its biogenesis depends on the main outer membrane protein translocase. TAC40 is a member of the mitochondrial porin family, whereas TAC42 represents a novel class of mitochondrial outer membrane β-barrel proteins. Consequently TAC40 and TAC42 contain C-terminal β-signals. Thus in trypanosomes the highly conserved β-barrel protein assembly machinery plays a major role in the biogenesis of its unique mitochondrial genome segregation system.