DNA in a single-stranded form (ssDNA) exists transiently within the cell and comprises the telomeres of linear chromosomes and the genomes of some DNA viruses. As with RNA, in the single-stranded state, some DNA sequences are able to fold into complex secondary and tertiary structures that may be recognized by proteins and participate in gene regulation. To better understand how such DNA elements might fold and interact with proteins, and to compare recognition features to those of a structured RNA, we used in vitro selection to identify ssDNAs that bind an RNA-binding peptide from the HIV Rev protein with high affinity and specificity. The large majority of selected binders contain a non-Watson-Crick G.T base-pair and an adjacent C:G base-pair and both are essential for binding. This GT motif can be presented in different DNA contexts, including a nearly perfect duplex and a branched three-helix structure, and appears to be recognized in large part by arginine residues separated by one turn of an alpha-helix. Interestingly, a very similar GT motif is necessary also for protein binding and function of a well-characterized model ssDNA regulatory element from the proenkephalin promoter.