Conjugation and deconjugation of ubiquitin and ubiquitin-like proteins (Ubls) to cellular proteins are highly regulated processes integral to cellular homeostasis. Most often, the C-termini of these small polypeptides are attached to lysine side chains of target proteins by an amide (isopeptide) linkage. Deubiquitinating enzymes (DUBs) and Ubl-specific proteases (ULPs) comprise a diverse group of proteases that recognize and remove ubiquitin and Ubls from their substrates. How DUBs and ULPs distinguish among different modifiers, or different polymeric forms of these modifiers, remains poorly understood. The specificity of ubiquitin/Ubl-deconjugating enzymes for particular substrates depends on multiple factors, ranging from the topography of specific substrate features, as in different polyubiquitin chain types, to structural elements unique to each enzyme. Here we summarize recent structural and biochemical studies that provide insights into mechanisms of substrate specificity among various DUBs and ULPs. We also discuss the unexpected specificities of non-eukaryotic proteases in these families.