Dnmt2 methylates cytosine at position 38 of tRNAAsp in a variety of eukaryotic organisms. A correlation between the presence of the hypermodified nucleoside queuosine (Q) at position 34 of tRNAAsp and the Dnmt2 dependent C38 methylation was recently found in vivo for S. pombe and D. discoideum. We demonstrate a direct effect of the Q-modification on the methyltransferase catalytic efficiency in vitro, as Vmax/K0.5 of purified S. pombe Dnmt2 shows an increase for in vitro transcribed tRNAAsp containing Q34 to 6.27 ∗ 10-3 s-1 µM-1 compared to 1.51 ∗ 10-3 s-1 µM-1 for the unmodified substrate. Q34tRNAAsp exhibits an only slightly increased affinity for Dnmt2 in comparison to unmodified G34tRNA. In order to get insight into the structural basis for the Q-dependency, the crystal structure of S. pombe Dnmt2 was determined at 1.7 Å resolution. It closely resembles the known structures of human and E. histolytica Dnmt2, and contains the entire active site loop. The interaction with tRNA was analyzed by means of mass-spectrometry using UV cross-linked Dnmt2-tRNA complex. These cross-link data and computational docking of Dnmt2 and tRNAAsp reveal Q34 positioned adjacent to the S-adenosylmethionine occupying the active site, suggesting that the observed increase of Dnmt2 catalytic efficiency by queuine originates from optimal positioning of the substrate molecules and residues relevant for methyl transfer.