The constitutive transport element (CTE) of type D retroviruses serves as a signal of nuclear export of unspliced viral RNAs. The human TAP(NXF1) protein, a cellular mRNA export factor, directly binds to CTE and mediates nuclear export of CTE-containing RNAs. Here, we use genomic SELEX (systematic evolution of ligands by exponential enrichment) to show that the human genome encodes a family of high-affinity TAP ligands. These TAP-binding elements (TBE) are 15-bp minisatellite repeats that are homologous to the core TAP-binding sites in CTE. The repeats are positioned similarly in the RNA secondary structures of CTE and TBE. Like CTE, TBE is an active nuclear export signal. CTE elements of different species share sequence similarities to TBE in the regions that are neutral for CTE function. This conservation points to a possible common ancestry of the two elements, and in fact, TBE has properties expected from a primordial CTE. Additionally, a molecular fossil of a TBE-like minisatellite is found in the genome of a modern retroelement. These findings constitute direct evidence of an evolutionary link between TBE-related minisatellites and CTE.