The trace element selenium is found in proteins as selenocysteine (Sec), the 21st amino acid to participate in ribosome-mediated translation. The substrate for ribosomal protein synthesis is selenocysteinyl-tRNASec. Its biosynthesis from seryl-tRNASec has been established for bacteria, but the mechanism of conversion from Ser-tRNASec remained unresolved for archaea and eukarya. Here, we provide evidence for a different route present in these domains of life that requires the tRNASec-dependent conversion of O-phosphoserine (Sep) to Sec. In this two-step pathway, O-phosphoseryl-tRNASec kinase (PSTK) converts Ser-tRNASec to SeptRNASec. This misacylated tRNA is the obligatory precursor for a Sep-tRNA:Sec-tRNA synthase (SepSecS); this protein was previously annotated as SLA/LP. The human and archaeal SepSecS genes complement in vivo an Escherichia coli Sec synthase (SelA) deletion strain. Furthermore, purified recombinant SepSecS converts SeptRNASec into Sec-tRNASec in vitro in the presence of sodiumselenite and purified recombinant E. coli selenophosphate synthetase (SelD). Phylogenetic arguments suggest that Sec decoding was present in the last universal common ancestor. SepSecS and PSTK coevolved with the archaeal and eukaryotic lineages, but the history of PSTK is marked by several horizontal gene transfer events, including transfer to non-Sec-decoding Cyanobacteria and fungi.