ExoU is a type III-secreted cytotoxin expressing A phospholipase activity when injected into eukaryotic target cells by the bacterium The enzymatic activity of ExoU is undetectable in vitro unless ubiquitin, a required cofactor, is added to the reaction. The role of ubiquitin in facilitating ExoU enzymatic activity is poorly understood but of significance for designing inhibitors to prevent tissue injury during infections with strains of producing this toxin. Most ubiquitin-binding proteins, including ExoU, demonstrate a low (micromolar) affinity for monoubiquitin (monoUb). Additionally, ExoU is a large and dynamic protein, limiting the applicability of traditional structural techniques such as NMR and X-ray crystallography to define this protein-protein interaction. Recent advancements in computational methods, however, have allowed high-resolution protein modeling using sparse data. In this study, we combine double electron-electron resonance (DEER) spectroscopy and Rosetta modeling to identify potential binding interfaces of ExoU and monoUb. The lowest-energy scoring model was tested using biochemical, biophysical, and biological techniques. To verify the binding interface, Rosetta was used to design a panel of mutations to modulate binding, including one variant with enhanced binding affinity. Our analyses show the utility of computational modeling when combined with sensitive biological assays and biophysical approaches that are exquisitely suited for large dynamic proteins.