Nuclear export of mRNA is mediated by interactions between soluble factors and nuclear pore complex (NPC) proteins. In Saccharomyces cerevisiae, Nab2 is an essential RNA-binding protein that shuttles between the nucleus and cytoplasm. The mechanism for trafficking of Nab2-bound mRNA through the NPC has not been defined. Gle1 is also required for mRNA export, and Gle1 interactions with NPC proteins, the RNA helicase Dbp5, and Gfd1 have been reported. Here we report that Nab2, Gfd1, and Gle1 associate in a complex. By using immobilized recombinant Gfd1, Nab2 was isolated from total yeast lysate. A similar biochemical assay with immobilized recombinant Nab2 resulted in coisolation of Gfd1 and Gle1. A Nab2-Gfd1 complex was also identified by coimmunoprecipitation from yeast lysates. In vitro binding assays with recombinant proteins revealed a direct association between Nab2 and Gfd1, and two-hybrid assays delineated Gfd1 binding to the N-terminal Nab2 domain. This N-terminal Nab2 domain is distinct from its RNA binding domains suggesting Nab2 could bind Gfd1 and RNA simultaneously. As Nab2 export was blocked in a gle1 mutant at the restrictive temperature, we propose a model wherein Gfd1 serves as a bridging factor between Gle1 and Nab2-bound mRNA during export.