The 21st amino acid, selenocysteine (Sec), is synthesized on its cognate transfer RNA (tRNA(Sec)). In bacteria, SelA synthesizes Sec from Ser-tRNA(Sec), whereas in archaea and eukaryotes SepSecS forms Sec from phosphoserine (Sep) acylated to tRNA(Sec). We determined the crystal structures of Aquifex aeolicus SelA complexes, which revealed a ring-shaped homodecamer that binds 10 tRNA(Sec) molecules, each interacting with four SelA subunits. The SelA N-terminal domain binds the tRNA(Sec)-specific D-arm structure, thereby discriminating Ser-tRNA(Sec) from Ser-tRNA(Ser). A large cleft is created between two subunits and accommodates the 3'-terminal region of Ser-tRNA(Sec). The SelA structures together with in vivo and in vitro enzyme assays show decamerization to be essential for SelA function. SelA catalyzes pyridoxal 5'-phosphate-dependent Sec formation involving Arg residues nonhomologous to those in SepSecS. Different protein architecture and substrate coordination of the bacterial enzyme provide structural evidence for independent evolution of the two Sec synthesis systems present in nature.