Determining how deubiquitinating enzymes discriminate between ubiquitin-conjugated substrates is critical to understand their function. Through application of a novel protein cleavage and tagging technique, sortagging, we show that human UCHL3 and the Plasmodium falciparum homologue, members of the ubiquitin C-terminal hydrolase family, use a unique active site crossover loop to restrict access of bulky ubiquitin adducts to the active site. Although it provides connectivity for critical active site residues in UCHL3, physical integrity of the crossover loop is dispensable for catalysis. By enlarging the active site crossover loop, we have constructed gain-of-function mutants that can accept substrates that the parent enzyme cannot, including ubiquitin chains of various linkages.