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-tRNA(Sec). Its biosynthesis from seryl-tRNA(Sec) has been established for bacteria, but the mechanism of conversion from Ser-tRNA(Sec) remained unresolved for archaea and eukarya. Here, we provide evidence for a different route present in these domains of life that requires the tRNA(Sec)-dependent conversion of O-phosphoserine (Sep) to Sec. In this two-step pathway, O-phosphoseryl-tRNA(Sec) kinase (PSTK) converts Ser-tRNA(Sec) to Sep-tRNA(Sec). 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 Sep-tRNA(Sec) into Sec-tRNA(Sec) in vitro in the presence of sodium selenite 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.