The nuclear pore complex (NPC) gates the only known conduit for molecular exchange between the nucleus and cytoplasm of eukaryotic cells. Macromolecular transport across the NPC is mediated by nucleocytoplasmic shuttling receptors termed karyopherins (Kaps). Kaps interact with NPC proteins (nucleoporins) that contain FG peptide repeats (FG Nups) and altogether carry hundreds of different cargoes across the NPC. Previously, we described a biochemical strategy to identify proteins that interact with individual components of the nucleocytoplasmic transport machinery. We used bacterially expressed fusions of GST with nucleoporins or karyopherins as bait to capture interacting proteins from yeast extracts. Forty-five distinct proteins were identified as binding to one or several FG Nups and Kaps. Most of the detected interactions were expected, such as Kap-Nup interactions, but others were unexpected, such as the interactions of the multi-subunit Nup84p complex with several of the FG Nups. Also unexpected were the interactions of various FG Nups with, the nucleoporins Nup2p and Nup133p, the Gsp1p-GTPase activating protein Rna1p, and the mRNA binding protein Pab1p. Here we resolve how these interactions occur. We show that Pab1p associates non-specifically with immobilized baits via RNA. More interestingly, we demonstrate that the Nup84p complex contains Nup133p as a subunit and binds to the FG repeat regions of Nups directly via the Nup85p subunit. Binding of Nup85p to the GLFG region of Nup116p was quantified in vitro (KD = 1.5 µM), and was confirmed in vivo using the yeast two-hybrid assay. We also demonstrate that Nup2p and Rna1p can be tethered directly to FG Nups via the importin Kap95p-Kap60p and the exportin Crm1p, respectively. We discuss possible roles of these novel interactions in the mechanisms of nucleocytoplasmic transport.