TET aminopeptidases assemble as large homo-dodecameric complexes. The reason why prokaryotic genomes often encode a diverse set of TET peptidases homologues remains unclear. In the archaeon Pyrococcus horikoshii, PhTET1, PhTET2 and PhTET3 homo-oligomeric particles have been proposed to work in concert to breakdown intracellular polypeptides. When coexpressed in Escherichia coli, the PhTET2 and PhTET3 proteins were found to assemble efficiently as heteromeric complexes. Biophysical analysis demonstrated that these particles possess the same quaternary structure as the homomeric TET dodecamers. The same hetero-oligomeric complexes were immunodetected in P. horikoshii cell extracts analysed by sucrose gradient fractionation and ion exchange chromatography. The biochemical activity of a purified hetero-oligomeric TET particle, assessed on chromogenic substrates and on a complex mixture of peptides, reveals that it displays higher efficiency than an equivalent combination of homo-oligomeric TET particles. Interestingly, phylogenetic analysis shows that PhTET2 and PhTET3 are paralogous proteins that arose from gene duplication in the ancestor of Thermococcales. Together, these results establish that the PhTET2 and PhTET3 proteins are two subunits of the same enzymatic complex aimed at the destruction of polypeptidic chains of very different composition. This is the first report for such a mechanism intended to improve multi-enzymatic complex efficiency among exopeptidases.