Wybutosine (yW), one of the most complicated modified nucleosides, is found in the anticodon loop of eukaryotic phenylalanine tRNA. This hypermodified nucleoside ensures correct codon recognition by stabilizing codon-anticodon pairings during the decoding process in the ribosome. TYW4 is an S-adenosylmethionine (SAM)-dependent enzyme that catalyzes the final step of yW biosynthesis, methylation and methoxycarbonylation. However, the structural basis for the catalytic mechanism by TYW4, and especially that for the methoxycarbonylation, have remained elusive. Here we report the apo and cofactor-bound crystal structures of yeast TYW4. The structures revealed that the C-terminal domain folds into a beta-propeller structure, forming part of the binding pocket for the target nucleoside. A comparison of the apo, SAM-bound, and S-adenosylhomocysteine-bound structures of TYW4 revealed a drastic structural change upon cofactor binding, which may sequester solvent from the catalytic site during the reaction and facilitate product release after the reaction. In conjunction with the functional analysis, our results suggest that TYW4 catalyzes both methylation and methoxycarbonylation at a single catalytic site, and in the latter reaction, the methoxycarbonyl group is formed through the fixation of carbon dioxide.