Ubiquitin binding domains (UBDs) are modular elements that bind non-covalently to ubiquitin and act as downstream effectors and amplifiers of the ubiquitination signal. With few exceptions, UBDs recognize the hydrophobic path centered on Ile44, including residues Leu8, Ile44, His68, and Val70. A variety of different orientations, which can be attributed to specific contacts between each UBD and surface residues surrounding the hydrophobic patch, specify how each class of UBD specifically contacts ubiquitin. Here, we describe the structural model of a novel ubiquitin-binding domain that we identified in NEDD4 binding protein 1 (N4BP1). By performing protein sequence analysis, mutagenesis, and nuclear magnetic resonance (NMR) spectroscopy of the 15N isotopically labeled protein, we demonstrate that a Phe-Pro motif in N4BP1 recognizes the canonical hydrophobic patch of ubiquitin. This recognition mode resembles the molecular mechanism evolved in the coupling of ubiquitin conjugation to endoplasmic-reticulum (ER) degradation (CUE) domain family, where an invariant proline, usually following a phenylalanine, is required for ubiquitin binding. Interestingly, this novel UBD, which is not evolutionary related to CUE domains, shares a 40% identity and 47% similarity with cullin binding domain associating with NEDD8 (CUBAN), a protein module that also recognizes the ubiquitin-like NEDD8. Based on these features, we dubbed the region spanning the C-terminal 50 residues of N4BP1 the CoCUN domain, for Cousin of CUBAN. By performing circular dichroism and 15N NMR chemical shift perturbation of N4BP1 in complex with ubiquitin, we demonstrate that the CoCUN domain lacks the NEDD8 binding properties observed in CUBAN. We also show that, in addition to mediating the interaction with ubiquitin and ubiquitinated substrates, both CUBAN and CoCUN are poly-ubiquitinated in cells. The structural and the functional characterization of this novel UBD can contribute to a deeper understanding of the molecular mechanisms governing N4BP1 function, providing at the same time a valuable tool for clarifying how the discrimination between ubiquitin and the highly related NEDD8 is achieved.