[Fe]-hydrogenase hosts an iron-guanylylpyridinol (FeGP) cofactor. The FeGP cofactor contains a pyridinol ring substituted with GMP, two methyl groups, and an acylmethyl group. HcgC, an enzyme involved in FeGP biosynthesis, catalyzes methyl transfer from S-adenosylmethionine (SAM) to C3 of 6-carboxymethyl-5-methyl-4-hydroxy-2-pyridinol (2). We report on the ternary structure of HcgC/S-adenosylhomocysteine (SAH, the demethylated product of SAM) and 2 at 1.7 angstrom resolution. The proximity of C3 of substrate 2 and the S atom of SAH indicates a catalytically productive geometry. The hydroxy and carboxy groups of substrate 2 are hydrogen-bonded with I115 and T179, as well as through a series of water molecules linked with polar and a few protonatable groups. These interactions stabilize the deprotonated state of the hydroxy groups and a keto form of substrate 2, through which the nucleophilicity of C3 is increased by resonance effects. Complemented by mutational analysis, a structure-based catalytic mechanism was proposed.