Breaking and forming peptidyl bonds are fundamental biochemical reactions in protein chemistry. Unlike proteases that are abundantly available, fast-acting ligases are rare. OaAEP1 is an enzyme isolated from the cyclotide-producing plant oldenlandia affinis that displayed weak peptide cyclase activity, despite having a similar structural fold with other asparaginyl endopeptidases (AEP). Here we report the first atomic structure of OaAEP1, at a resolution of 2.56 Å, in its preactivation form. Our structure and biochemical analysis of this enzyme reveals its activation mechanism as well as structural features important for its ligation activity. Importantly, through structure-based mutagenesis of OaAEP1, we obtained an ultrafast variant having hundreds of times faster catalytic kinetics, capable of ligating well-folded protein substrates using only a submicromolar concentration of enzyme. In contrast, the protein-protein ligation activity in the original wild-type OaAEP1 enzyme described previously is extremely weak. Thus, the structure-based engineering of OaAEP1 described here provides a unique and novel recombinant tool that can now be used to conduct various protein labeling and modifications that were extremely challenging before.