Y14 and Mago are conserved eukaryotic proteins that associate with spliced mRNAs in the nucleus and remain associated at exon junctions during and after nuclear export. In the cytoplasm, Y14 is involved in mRNA quality control via the nonsense-mediated mRNA decay (NMD) pathway and, together with Mago, is involved in localization of osk (oskar) mRNA. We have determined the crystal structure of the complex between Drosophila melanogaster Y14 and Mago at a resolution of 2.5 A. The structure reveals an atypical mode of protein-protein recognition mediated by an RNA-binding domain (RBD). Instead of binding RNA, the RBD of Y14 engages its RNP1 and RNP2 motifs to bind Mago. Using structure-guided mutagenesis, we show that Mago is also a component of the NMD pathway, and that its association with Y14 is essential for function. Heterodimerization creates a single structural platform that interacts with the NMD machinery via phylogenetically conserved residues.