Only a minority of currently known protein families is characterized structurally. This makes homology-based structure modeling an essential instrument that can be viewed as the first approximation to experimental determination of protein structure. Using sequence similarity searches, we detected a distant similarity between a family of uncharacterized hypothetical proteins, COG4849, and the family of tRNA nucleotidyltransferases. The suggested remote homology between the N-terminal domain of COG4849 and the catalytic domain of tRNA nucleotidyltransferase was further supported by comparison of sequence profiles, methods for fold recognition and structure modeling. The combined multiple alignment of the two families reveals shared conservation of functionally important motifs and suggests the similarity in catalytic mechanisms of the performed reactions. Our results suggest that (i) the N-terminal domain of proteins from COG4849 shares structural similarity with the catalytic domain of tRNA nucleotidyltransferase, and (ii) this domain catalyzes the nucleotidyl transfer reaction involving two metal ions.