The Mixed-Lineage Leukemia gene (MLL/HRX/ALL1) encodes a large nuclear protein homologous to Drosophila trithorax that is required for the maintenance of HOX gene expression. MLL is cleaved at two conserved sites generating N320 and C180 fragments, which heterodimerize to stabilize the complex and confer its subnuclear destination. Here, we purify and clone the protease responsible for cleaving MLL. We entitle it Taspase1 as it initiates a class of endopeptidases that utilize an N-terminal threonine as the active site nucleophile to proteolyze polypeptide substrates following aspartate. Taspase1 proenzyme is intramolecularly proteolyzed generating an active 28 kDa α/22 kDa β heterodimer. RNAi-mediated knockdown of Taspase1 results in the appearance of unprocessed MLL and the loss of proper HOX gene expression. Taspase1 coevolved with MLL/trithorax as Arthropoda and Chordata emerged from Metazoa suggesting that Taspase1 originated to regulate complex segmental body plans in higher organisms.