Stress induces changes of modified nucleosides in tRNA, and these changes can influence codon-anticodon interaction and therefore the translation of target proteins. Certain nucleoside modification genes are associated with regulation of stress tolerance and immune response in plants. In this study, we found a dramatic increase of 2′-O-methyladenosine (Am) nucleoside in rice seedlings subjected to salt stress and abscisic acid (ABA) treatment. We identified LOC-Os03g61750 (OsTRM13) as a rice candidate methyltransferase for the Am modification. OsTRM13 transcript levels increased significantly upon salt stress and ABA treatment, and the OsTrm13 protein was found to be located primarily to the nucleus. More importantly, OsTRM13 overexpression plants displayed improved salt stress tolerance, and vice versa, OsTRM13 RNA interference (RNAi) plants showed reduced tolerance. Furthermore, OsTRM13 complemented a yeast trm13? mutant, deficient in Am synthesis, and the purified OsTrm13 protein catalysed Am nucleoside formation on tRNA-Gly-GCC in vitro. Our results show that OsTRM13, encoding a rice tRNA nucleoside methyltransferase, is an important regulator of salt stress tolerance in rice.