Trailer Hitch (Tral or LSm15) and enhancer of decapping-3 (EDC3 or LSm16) are conserved eukaryotic members of the (L)Sm (Sm and Like-Sm) protein family. They have a similar domain organization, characterized by an N-terminal LSm domain and a central FDF motif; however, in Tral, the FDF motif is flanked by regions rich in charged residues, whereas in EDC3 the FDF motif is followed by a YjeF_N domain. We show that in Drosophila cells, Tral and EDC3 specifically interact with the decapping activator DCP1 and the DEAD-box helicase Me31B. Nevertheless, only Tral associates with the translational repressor CUP, whereas EDC3 associates with the decapping enzyme DCP2. Like EDC3, Tral interacts with DCP1 and localizes to mRNA processing bodies (P bodies) via the LSm domain. This domain remains monomeric in solution and adopts a divergent Sm fold that lacks the characteristic N-terminal alpha-helix, as determined by nuclear magnetic resonance analyses. Mutational analysis revealed that the structural integrity of the LSm domain is required for Tral both to interact with DCP1 and CUP and to localize to P-bodies. Furthermore, both Tral and EDC3 interact with the C-terminal RecA-like domain of Me31B through their FDF motifs. Together with previous studies, our results show that Tral and EDC3 are structurally related and use a similar mode to associate with common partners in distinct protein complexes.