The specification of both the germ line and abdomen in Drosophila depends on the localization of oskar messenger RNA to the posterior of the oocyte. This localization requires several trans-acting factors, including Barentsz and the Mago-Y14 heterodimer, which assemble with oskar mRNA into ribonucleoprotein particles (RNPs) and localize with it at the posterior pole. Although Barentsz localization in the germ line depends on Mago-Y14, no direct interaction between these proteins has been detected. Here, we demonstrate that the translation initiation factor eIF4AIII interacts with Barentsz and is a component of the oskar messenger RNP localization complex. Moreover, eIF4AIII interacts with Mago-Y14 and thus provides a molecular link between Barentsz and the heterodimer. The mammalian Mago (also known as Magoh)-Y14 heterodimer is a component of the exon junction complex. The exon junction complex is deposited on spliced mRNAs and functions in nonsense-mediated mRNA decay (NMD), a surveillance mechanism that degrades mRNAs with premature translation-termination codons. We show that both Barentsz and eIF4AIII are essential for NMD in human cells. Thus, we have identified eIF4AIII and Barentsz as components of a conserved protein complex that is essential for mRNA localization in flies and NMD in mammals.