The parasite Trypanosoma brucei, the causative agent of sleeping sickness across sub-Saharan Africa, depends on a remarkable U-insertion/deletion RNA editing process in its mitochondrion. A approximately 20 S multi-protein complex, called the editosome, is an essential machinery for editing pre-mRNA molecules encoding the majority of mitochondrial proteins. Editosomes contain a common core of twelve proteins where six OB-fold interaction proteins, called A1-A6, play a crucial role. Here, we report the structure of two single-strand nucleic acid-binding OB-folds from interaction proteins A3 and A6 that surprisingly, form a heterodimer. Crystal growth required the assistance of an anti-A3 nanobody as a crystallization chaperone. Unexpectedly, this anti-A3 nanobody binds to both A3(OB) and A6, despite only ~40% amino acid sequence identity between the OB-folds of A3 and A6. The A3(OB)-A6 heterodimer buries 35% more surface area than the A6 homodimer. This is attributed mainly to the presence of a conserved Pro-rich loop in A3(OB). The implications of the A3(OB)-A6 heterodimer, and of a dimer of heterodimers observed in the crystals, for the architecture of the editosome are profound, resulting in a proposal of a 'five OB-fold center' in the core of the editosome.