RNA molecules that bind tightly and specifically to a Rex fusion protein have been isolated from a conformationally constrained pool of random sequence RNAs. The anti-Rex aptamers effectively mimic several features of the wild-type Rex-binding element (XBE). The highest-affinity aptamers effectively compete with the wild-type XBE for binding to the RNA-binding domain of Rex, an arginine-rich motif (ARM), but do not bind to the functionally analogous Rev protein or its ARM. However, characteristic sequence and structural motifs found in some of the anti-Rex aptamers may provide insights into how the Rex protein can interact with other viral RNAs, such as the Rev-responsive element. The anti-Rex aptamers can functionally substitute for the XBE in vivo, a result which supports a previously proposed model for mRNA transport in which the viral genome serves as a platform for assembling a nucleoprotein complex that can co-opt the cellular transport apparatus. Overall, these studies suggest that anti-Rex aptamers may serve as RNA decoys of the Rex protein.