Proteins crucial for the respiratory chain are translated by the mitochondrial ribosome. Mitochondrial ribosome biogenesis is therefore critical for oxidative phosphorylation capacity and disturbances are known to cause human disease. This complex process is evolutionary conserved and involves several RNA processing and modification steps required for correct ribosomal RNA maturation. We recently showed that a member of the mitochondrial transcription termination factor (MTERF) family of proteins, MTERF4, recruits NSUN4, a 5-methylcytosine RNA methyltransferase, to the large ribosomal subunit in a process crucial for mitochondrial ribosome biogenesis. Here, we describe the 3D crystal structure of the human MTERF4-NSUN4 complex determined to 2.9 Å resolution. MTERF4 is composed of structurally repeated MTERF-motifs that form a nucleic acid binding domain. NSUN4 lacks an N- or C-terminal extension that is commonly used for RNA recognition by related RNA methyltransferases. Instead, NSUN4 binds to the C-terminus of MTERF4. A positively charged surface forms an RNA binding path from the concave to the convex side of MTERF4 and further along NSUN4 all of the way into the active site. This finding suggests that both subunits of the protein complex likely contribute to RNA recognition. The interface between MTERF4 and NSUN4 contains evolutionarily conserved polar and hydrophobic amino acids, and mutations that change these residues completely disrupt complex formation. This study provides a molecular explanation for MTERF4-dependent recruitment of NSUN4 to ribosomal RNA and suggests a unique mechanism by which other members of the large MTERF-family of proteins can regulate ribosomal biogenesis.