The recent discovery of an alternate pathway for indirectly charging tRNA(Cys) has stimulated a re-examination of the evolutionary history of Cys-tRNA(Cys) formation. In the first step of the pathway, O-phosphoseryl-tRNA synthetase charges tRNA(Cys) with O-phosphoserine (Sep), a precursor of the cognate amino acid. In the following step, Sep-tRNA:Cys-tRNA synthase (SepCysS) converts Sep to Cys in a tRNA-dependent reaction. The existence of such a pathway raises several evolutionary questions, including whether the indirect pathway is a recent evolutionary invention, as might be implied from its localization to the Euryarchaea, or, as evidence presented here indicates, whether this pathway is more ancient, perhaps already in existence at the time of the last universal common ancestral state. A comparative phylogenetic approach is used, combining evolutionary information from protein sequences and structures, that takes both the signature of horizontal gene transfer and the recurrence of the full canonical phylogenetic pattern into account, to document the complete evolutionary history of cysteine coding and understand the nature of this process in the last universal common ancestral state. Resulting from the historical study of tRNA(Cys) aminoacylation and the integrative perspective of sequence, structure, and function are 3D models of O-phosphoseryl-tRNA synthetase and SepCysS, which provide experimentally testable predictions regarding the identity and function of key active-site residues in these proteins. The model of SepCysS is used to suggest a sulfhydrylation reaction mechanism, which is predicted to occur at the interface of a SepCysS dimer.