Mitochondrial gene expression uses a non-universal genetic code in mammals. Besides reading the conventional AUG codon, mitochondrial (mt-)tRNA mediates incorporation of methionine on AUA and AUU codons during translation initiation and on AUA codons during elongation. We show that the RNA methyltransferase NSUN3 localises to mitochondria and interacts with mt-tRNA to methylate cytosine 34 (C34) at the wobble position. NSUN3 specifically recognises the anticodon stem loop (ASL) of the tRNA, explaining why a mutation that compromises ASL basepairing leads to disease. We further identify ALKBH1/ABH1 as the dioxygenase responsible for oxidising mC34 of mt-tRNA to generate an fC34 modification. In vitro codon recognition studies with mitochondrial translation factors reveal preferential utilisation of mC34 mt-tRNA in initiation. Depletion of either NSUN3 or ABH1 strongly affects mitochondrial translation in human cells, implying that modifications generated by both enzymes are necessary for mt-tRNA function. Together, our data reveal how modifications in mt-tRNA are generated by the sequential action of NSUN3 and ABH1, allowing the single mitochondrial tRNA to recognise the different codons encoding methionine.