Escherichia coli ribosomal protein S15 recognizes two RNA targets: a three-way junction in 16S rRNA and a pseudoknot structure on its own mRNA. Binding to mRNA occurs when S15 is expressed in excess over its rRNA target, resulting in an inhibition of translation start. The sole apparent similarity between the rRNA and mRNA targets is the presence of a G-U/G-C motif that contributes only modestly to rRNA binding but is essential for mRNA. To get more information on the structural determinants used by S15 to bind its mRNA target as compared to its rRNA site, we used site-directed mutagenesis, substitution by nucleotide analogs, footprinting experiments on both RNA and protein, and graphic modeling. The size of the mRNA-binding site could be reduced to 45 nucleotides, without loss of affinity. This short RNA preferentially folds into a pseudoknot, the formation of which depends on magnesium concentration and temperature. The size of the loop L2 that bridges the two stems of the pseudoknot through the minor groove could not be reduced below nine nucleotides. Then we showed that the pseudoknot recognizes the same side of S15 as 16S rRNA, although shielding a smaller surface area. It turned out that the G-U/G-C motif is recognized from the minor groove in both cases, and that the G-C pair is recognized in a very similar manner. However, the wobble G-U pair of the mRNA is not directly contacted by S15, as in rRNA, but is most likely involved in building a precise conformation of the RNA, essential for binding. Otherwise, unique specific features are utilized, such as the three-way junction in the case of 16S rRNA and the looped out A(-46) for the mRNA pseudoknot.