The cloverleaf structure in the 5'-untranslated region of enterovirus RNA that regulates viral RNA replication contains an evolutionarily conserved YNMG tetraloop closed by a Y-G base pair. This loop is believed to interact specifically with the viral protease 3C. To further characterize the specificity of this interaction, the tetraloop and two flanking base pairs of the poliovirus RNA were randomized, and viable viral clones were obtained using in vivo SELEX. Among many different mutants with the canonical YNMG sequences to be described elsewhere, a large-plaque-forming clone contained a deviating uGCUAg sequence. The NMR structure of a small hairpin capped with uGCUAg that we present here shows that the GCUA tetraloop adopts a novel fold, which is highly similar to that of the YNMG tetraloop with common stacking properties and hydrogen-bond interactions including an unusual syn conformation of the adenosine. Thermodynamic studies show moderate stabilities of hairpins with canonical YNMG and the novel GCUA loops, which, together with the similarity of spatial structures, illustrates that the tetraloop structure itself is crucial for the RNA-protein interaction required for the viral replication. A re-evaluation of the ribosomal secondary structure database reveals a hairpin containing a GCUA loop, which covaries with YNMG and is involved in a tertiary interaction, and in the 50S ribosomal subunit from Haloarcula marismortui the structurally comparable apex of stem-loop 35a is a recognition site for protein L2. These observations show a more general occurrence and importance of the so-far unrecognized GYYA hairpin loops.