Xpo1p (Crm1p) is the nuclear export receptor for proteins containing a leucine-rich nuclear export signal (NES). Xpo1p, the NES-containing protein, and GTP-bound Ran form a complex in the nucleus that translocates across the nuclear pore. We have identified Yrb1p as the major Xpo1p-binding protein in Saccharomyces cerevisiae extracts in the presence of GTP-bound Gsp1p (yeast Ran). Yrb1p is cytoplasmic at steady-state but shuttles continuously between the cytoplasm and the nucleus. Nuclear import of Yrb1p is mediated by two separate nuclear targeting signals. Export from the nucleus requires Xpo1p, but Yrb1p does not contain a leucine-rich NES. Instead, the interaction of Yrb1p with Xpo1p is mediated by Gsp1p-GTP. This novel type of export complex requires the acidic C-terminus of Gsp1p, which is dispensable for the binding to importin β-like transport receptors. A similar complex with Xpo1p and Gsp1p-GTP can be formed by Yrb2p, a relative of Yrb1p predominantly located in the nucleus. Yrb1p also functions as a disassembly factor for NES/Xpo1p/Gsp1p-GTP complexes by displacing the NES protein from Xpo1p/Gsp1p. This Yrb1p/Xpo1p/Gsp1p complex is then completely dissociated after GTP hydrolysis catalyzed by the cytoplasmic GTPase activating protein Rna1p.