Nonsense-mediated mRNA decay (NMD) is a quality control mechanism that detects and degrades mRNAs containing premature stop codons (PTCs). In vertebrates, PTCs trigger efficient NMD when located upstream of an exon junction complex (EJC). Degradation of PTC-containing mRNAs requires the endonucleolytic activity of SMG6, a conserved NMD factor; nevertheless, the precise role for the EJC in NMD and how the SMG6 endonuclease is recruited to NMD targets have been unclear. Here we show that SMG6 interacts directly with the EJC via two conserved EJC-binding motifs (EBMs). We further show that the SMG6-EJC interaction is required for NMD. Our results reveal an unprecedented role for the EJC in recruiting the SMG6 endonuclease to NMD targets. More generally, our findings identify the EBM as a protein motif present in a handful of proteins, and suggest that EJCs establish multiple and mutually exclusive interactions with various protein partners, providing a plausible explanation for the myriad functions performed by this complex in post-transcriptional mRNA regulation.