Npl4 is likely to be the most upstream factor recognizing Lys48-linked polyubiquitylated substrates in the proteasomal degradation pathway in yeast. Along with Ufd1, Npl4 forms a heterodimer (UN), and functions as a cofactor for the Cdc48 ATPase. Here, we report the crystal structures of yeast Npl4 in complex with Lys48-linked diubiquitin and with the Npl4-binding motif of Ufd1. The distal and proximal ubiquitin moieties of Lys48-linked diubiquitin primarily interact with the C-terminal helix and N-terminal loop of the Npl4 C-terminal domain (CTD), respectively. Mutational analysis suggests that the CTD contributes to linkage selectivity and initial binding of ubiquitin chains. Ufd1 occupies a hydrophobic groove of the Mpr1/Pad1 N-terminal (MPN) domain of Npl4, which corresponds to the catalytic groove of the MPN domain of JAB1/MPN/Mov34 metalloenzyme (JAMM)-family deubiquitylating enzyme. This study provides important structural insights into the polyubiquitin chain recognition by the Cdc48-UN complex and its assembly.