Selenocysteine (Sec) is the 21st amino acid in the genetic code, inserted in response to UGA codons with the help of RNA structures, the SEC Insertion Sequence (SECIS) elements. The three domains of life feature distinct strategies for Sec insertion in proteins and its utilization. While bacteria and archaea possess similar sets of selenoproteins, Sec biosynthesis is more similar among archaea and eukaryotes. However, SECIS elements are completely different in the three domains of life. Here, we analyze the archaeon Lokiarchaeota that resolves the relationships among Sec insertion systems. This organism has selenoproteins representing five protein families, three of which have multiple Sec residues. Remarkably, these archaeal selenoprotein genes possess conserved RNA structures that strongly resemble the eukaryotic SECIS element, including key eukaryotic protein-binding sites. These structures also share similarity with the SECIS element in archaeal selenoprotein VhuD, suggesting a relation of direct descent. These results identify Lokiarchaeota as an intermediate form between the archaeal and eukaryotic Sec-encoding systems and clarify the evolution of the Sec insertion system.