Proteins containing selenocysteine are found in members of all three domains of life, Bacteria, Eukarya and Archaea. A dedicated tRNA (tRNA ^sec) serves as a scaffold for selenocysteine synthesis. However, sequence and secondary structures differ in tRNA ^sec from the different domains. An Escherichia coli strain lacking the gene for tRNA ^sec could only be complemented with the homologue from Methanococcus maripaludis when a single base in the anticodon loop was exchanged demonstrating that this base is a crucial determinant for archaeal tRNA ^sec to function in E. coli. Complementation in trans of M. maripaludis JJ mutants lacking tRNA ^sec, O-phosphoseryl-tRNA ^sec kinase or O-phosphoseryl-tRNA ^sec:selenocysteine synthase with the corresponding genes from M. maripaludis S2 restored the mutant's ability to synthesize selenoproteins. However, only partial restoration of the wild-type selenoproteome was observed as only selenocysteine-containing formate dehydrogenase was synthesized. Quantification of transcripts showed that disrupting the pathway of selenocysteine synthesis leads to downregulation of selenoprotein gene expression, concomitant with upregulation of a selenium-independent backup system, which is not re-adjusted upon complementation. This transcriptional arrest was independent of selenophosphate but depended on the 'history' of the mutants and was inheritable, which suggests that a stable genetic switch may cause the resulting hierarchy of selenoproteins synthesized.