Nematode mitochondria possess extremely truncated tRNAs. Of 22 tRNAs, 20 lack the entire T-arm. The T-arm is necessary for the binding of canonical tRNAs and EF (elongation factor)-Tu (thermo-unstable). The nematode mitochondrial translation system employs two different EF-Tu factors named EF-Tu1 and EF-Tu2. Our previous study showed that nematode Caenorhabditis elegans EF-Tu1 binds specifically to T-armless tRNA. C. elegans EF-Tu1 has a 57-amino acid C-terminal extension that is absent from canonical EF-Tu, and the T-arm-binding residues of canonical EF-Tu are not conserved. In this study, the recognition mechanism of T-armless tRNA by EF-Tu1 was investigated. Both modification interference assays and primer extension analysis of cross-linked ternary complexes revealed that EF-Tu1 interacts not only with the tRNA acceptor stem but also with the D-arm. This is the first example of an EF-Tu recognizing the D-arm of a tRNA. The binding activity of EF-Tu1 was impaired by deletion of only 14 residues from the C-terminus, indicating that the C-terminus of EF-Tu1 is required for its binding to T-armless tRNA. These results suggest that C. elegans EF-Tu1 recognizes the D-arm instead of the T-arm by a mechanism involving its C-terminal region. This study sheds light on the co-evolution of RNA and RNA-binding proteins in nematode mitochondria.