Cells have evolved mutagenic bypass mechanisms that prevent stalling of the replication machinery at DNA lesions. This process, translesion DNA synthesis (TLS), involves switching from high-fidelity DNA polymerases to specialized DNA polymerases that replicate through a variety of DNA lesions. In eukaryotes, polymerase switching during TLS is regulated by the DNA damage-triggered monoubiquitylation of PCNA. How the switch operates is unknown, but all TLS polymerases of the so-called Y-family possess PCNA and ubiquitin-binding domains that are important for their function. To gain insight into the structural mechanisms underlying the regulation of TLS by ubiquitylation, we have probed the interaction of ubiquitin with a conserved ubiquitin-binding motif (UBM2) of Y-family polymerase Poliota. Using NMR spectroscopy, we have determined the structure of a complex of human Poliota UBM2 and ubiquitin, revealing a novel ubiquitin recognition fold consisting of two alpha-helices separated by a central trans-proline residue conserved in all UBMs. We show that, different from the majority of ubiquitin complexes characterized to date, ubiquitin residue Ile44 only plays a modest role in the association of ubiquitin with Poliota UBM2. Instead, binding of UBM2 is centered on the recognition of Leu8 in ubiquitin, which is essential for the interaction.