The constitutive transport element (CTE) of the type D retroviruses promotes nuclear export of unspliced viral RNAs by recruiting host factor(s) required for export of cellular messenger RNAs. Recently, the human Tap protein was shown to specifically bind to the CTE in vitro, and stimulate CTE-dependent mRNA export in Xenopus oocytes. Mex67p, the yeast homolog of Tap, is also involved in the nuclear export of yeast cellular mRNAs. Using the yeast three-hybrid system and a HIV-1 Tat-based mammalian RNA binding assay system, we demonstrate that Tap binds to the CTE specifically in vivo, and that the central domain of amino acid 20-312 is necessary and sufficient for RNA binding. Hela cell microinjection experiments using GST fusion proteins of various portions of Tap indicate that there are two nuclear localization signals in Tap, one at each ends of the protein. However, neither of these has any obvious similarity to known nuclear localization signals. The C-terminal NLS of Tap (aa 480-559) also functions as a potent nuclear export signal. We have designed a novel in vivo randomization/selection strategy to obtain several RNA sequence variants of CTE that can still be recognized by Tap. All these variants can functionally substitute for wild-type CTE in the nuclear export of mRNA, rhus strongly suggesting that Tap is indeed the genuine nuclear export cofactor for CTE.