The nuclear exosome and the associated RNA helicase Mtr4 participate in the processing of several ribonucleoprotein particles (RNP), including the maturation of the large ribosomal subunit (60S). S. cerevisiae Mtr4 interacts directly with Nop53, a ribosomal biogenesis factor present in late pre-60S particles containing precursors of the 5.8S rRNA. The Mtr4–Nop53 interaction plays a pivotal role in the maturation of the 5.8S rRNA, providing a physical link between the nuclear exosome and the pre-60S RNP. An analogous interaction between Mtr4 and another ribosome biogenesis factor, Utp18, directs the exosome to an earlier preribosomal particle. Nop53 and Utp18 contain a similar Mtr4-binding motif known as the arch-interacting motif (AIM). Here, we report the 3.2 Å resolution crystal structure of S. cerevisiae Mtr4 bound to the interacting region of Nop53, revealing how the KOW domain of the helicase recognizes the AIM sequence of Nop53 with a network of hydrophobic and electrostatic interactions. The AIM-interacting residues are conserved in Mtr4 and are not present in the related cytoplasmic helicase Ski2, rationalizing the specificity and versatility of Mtr4 in the recognition of different AIM-containing proteins. Using nuclear magnetic resonance (NMR), we show that the KOW domain of Mtr4 can simultaneously bind an AIM-containing protein and a structured RNA at adjacent surfaces, suggesting how it can dock onto RNPs. The KOW domains of exosome-associated helicases thus appear to have evolved from the KOW domains of ribosomal proteins and to function as RNP-binding modules in the context of the nuclear exosome.