Protein-protein interactions (PPIs) are inherently dynamic and vital for maintaining normal cellular function. Short linear motifs (SLiMs), which are typically 3-10 amino acid long stretches, are present in intrinsically disordered regions (IDRs) and often serve as binding interfaces for PPIs. SLiM-mediated interactions are essential in various biological processes, such as cellular signaling, cell cycle progression and protein degradation. SLiMs play an important role in targeting E3 ligases to their substrates. They may also recruit deubiquitinating enzymes (DUBs) to their substrates, thereby reversing the action of E3 ligases by removing ubiquitin from target proteins.  At present, only a fraction of the predicted SLiMs in the human proteome has been identified. Thus, it is important to develop and utilize methods to identify SLiM-based interactions and to gain further insights into the specificity determinants of the interactions. Proteomic peptide-phage display (ProP-PD) is a high-throughput method developed to capture motif-based PPIs. However, sometimes only a limited set of peptide ligands are identified from these experiments, rendering it challenging to define a consensus binding motif. We therefore developed a deep-mutational scanning (DMS) by peptide-phage display approach, which enables comprehensive examination of the effects of substitutions on peptide-protein interactions. Using the DMS protocol, we deciphered the binding determinants of motif-based interactions of two globular domains of the ubiquitin carboxyl-terminal hydrolase 8 (USP8). We uncovered that the MIT domain, which is a previously described motif-binding domain, binds to degenerate motif variants. Furthermore, we revealed a peptide binding capability of the Rhodanese domain and demonstrated that it recognizes more than one type of motif. The information enabled the prediction of potential binding sites in USP8 known interactors. Expanding the analysis to other DUBs, a screening for additional motif-binding auxiliary domains of proteins from the USP family was performed. Fourteen domains were found to bind to peptides, which expanded the previously unexplored landscape of DUB-motif recognition. The zf-UBP and DUSP2 domains of USP20 and USP33 were found to act as peptide-binding domains, recognizing novel consensus motifs. Finally, extending beyond DUBs, a contribution was made towards charting interactions for numerous peptide-binding domains. The research presented in this thesis, sheds light on the previously underexplored area of motif-recognition of DUBs and contributes towards expanding the motif-based map of the human interactome.