Establishment of the early genetic code likely required strategies to ensure translational accuracy and inevitably involved tRNA post-transcriptional modifications. One such modification, wybutosine/wyosine is crucial for translational fidelity in Archaea and Eukarya; yet it does not occur in Bacteria and has never been described in mitochondria. Here, we present genetic, molecular and mass spectromery data demonstrating the first example of wyosine in mitochondria, a situation thus far unique to kinetoplastids. We also show that these modifications are important for mitochondrial function, underscoring their biological significance. This work focuses on TyW1, the enzyme required for the most critical step of wyosine biosynthesis. Based on molecular phylogeny, we suggest that the kinetoplastids pathways evolved via gene duplication and acquisition of an FMN-binding domain now prevalent in TyW1 of most eukaryotes. These findings are discussed in the context of the extensive U-insertion RNA editing in trypanosome mitochondria, which may have provided selective pressure for maintenance of mitochondrial wyosine in this lineage.