Ubiquitination, a modification in which single or multiple ubiquitin molecules are attached to a protein, serves signaling functions that control several cellular processes. The ubiquitination signal is recognized by downstream effectors, many of which carry a ubiquitin-interacting motif (UIM). Such interactions can be modulated by regulators carrying a ubiquitin-like (UbL) domain, which binds UIM by mimicking ubiquitination. Of them, HR23B regulates the proteasomal targeting of ubiquitinated substrates, DNA repair factors, and other proteins. Here we report the structure of the UIM of the proteasome subunit S5a bound to the UbL domain of HR23B. The UbL domain presents one hydrophobic and two polar contact sites for interaction with UIM. The residues in these contact sites are well conserved in ubiquitin, but ubiquitin also presents a histidine at the interface. The pH-dependent protonation of this residue interferes with the access of ubiquitin to the UIM and the ubiquitin-associated domain (UBA), and its mutation to a smaller residue increases the affinity of ubiquitin for UIM.