The highly conserved Elongator complex modifies transfer RNAs (tRNAs) in their wobble base position, thereby regulating protein synthesis and ensuring proteome stability. The precise mechanisms of tRNA recognition and its modification reaction remain elusive. Here, we show cryo-electron microscopy structures of the catalytic subcomplex of Elongator and its tRNA-bound state at resolutions of 3.3 and 4.4 Å. The structures resolve details of the catalytic site, including the substrate tRNA, the iron-sulfur cluster, and a SAM molecule, which are all validated by mutational analyses in vitro and in vivo. tRNA binding induces conformational rearrangements, which precisely position the targeted anticodon base in the active site. Our results provide the molecular basis for substrate recognition of Elongator, essential to understand its cellular function and role in neurodegenerative diseases and cancer.