Binding of Escherichia coli signal recognition particle (SRP) to its receptor, FtsY, requires the presence of 4.5S RNA, although FtsY alone does not interact with 4.5S RNA. In this study, we report that the exchange of the GGAA tetraloop sequence in domain IV of 4.5S RNA for UUCG abolishes SRP-FtsY interaction, as determined by gel retardation and membrane targeting experiments, whereas replacements with other GNRA-type tetraloops have no effect. A number of other base exchanges in the tetraloop sequence have minor or intermediate inhibitory effects. Base pair disruptions in the stem adjacent to the tetraloop or replacement of the closing C-G base pair with G-C partially restored function of the otherwise inactive UUCG mutant. Chemical probing by hydroxyl radical cleavage of 4.5S RNA variants show that replacing GGAA with UUCG in the tetraloop sequence leads to structural changes both within the tetraloop and in the adjacent stem; the latter change is reversed upon reverting the C-G closing base pair to G-C. These results show that the SRP-FtsY interaction is strongly influenced by the structure of the tetraloop region of SRP RNA, in particular the tetraloop stem, and suggest that both SRP RNA and Ffh undergo mutual structural adaptation to form SRP that is functional in the interaction with the receptor, FtsY.