The 26S proteasome is essential for the proteolysis of proteins that have been covalently modified by the attachment of polyubiquitinated chains. Although the 20S core particle performs the degradation, the 19S regulatory cap complex is responsible for recognition of polyubiquitinated substrates. We have focused on how the S5a component of the 19S complex interacts with different ubiquitin-like (ubl) modules, to advance our understanding of how polyubiquitinated proteins are targeted to the proteasome. To achieve this, we have determined the solution structure of the ubl domain of hPLIC-2 and obtained a structural model of hHR23a by using NMR spectroscopy and homology modeling. We have also compared the S5a binding properties of ubiquitin, SUMO-1, and the ubl domains of hPLIC-2 and hHR23a and have identified the residues on their respective S5a contact surfaces. We provide evidence that the S5a-binding surface on the ubl domain of hPLIC-2 is required for its interaction with the proteasome. This study provides structural insights into protein recognition by the proteasome, and illustrates how the protein surface of a commonly utilized fold has highly evolved for various biological roles.