To investigate the stringency of the Escherichia coli selenocysteine insertion sequence (SECIS) requirements, libraries of SECIS variants were screened via a novel method in which suppression of the selenocysteine (Sec) opal codon was coupled to bacteriophage plaque formation. The SECIS variant libraries were designed with a mostly paired lower stem, so that randomization could be focused on the upper stem and loop regions. We identified 19 functional non-native SECIS sequences that violated the expected pairing requirements for the SECIS upper stem. All of the SECIS variants were shown to permit Sec insertion in phage (by chemical modification of the Sec residue) and fused to lacZalpha (by beta-galactosidase assay). The diminished pairing of the upper stem appears to be mitigated by the overall stem stability; a given upper stem variant has significantly higher readthrough in the context of a paired, rather than unpaired, lower stem. These results suggest an unexpected downstream sequence flexibility in prokaryotic selenoprotein expression.