Polyadenylation of mRNA precursors is a two-step reaction requiring multiple protein factors. Cleavage stimulation factor (CstF) is a heterotrimer necessary for the first step, endonucleolytic cleavage, and it plays an important role in determining the efficiency of polyadenylation. Although a considerable amount is known about the RNA binding properties of CstF, the protein-protein interactions required for its assembly and function are poorly understood. We therefore first identified regions of the CstF subunits, CstF-77, CstF-64, and CstF-50, required for interaction with each other. Unexpectedly, small regions of two of the subunits participate in multiple interactions. In CstF-77, a proline-rich domain is necessary not only for binding both other subunits but also for self-association, an interaction consistent with genetic studies in Drosophila. In CstF-64, a small region, highly conserved in metazoa, is responsible for interactions with two proteins, CstF-77 and symplekin, a nuclear protein of previously unknown function. Intriguingly, symplekin has significant similarity to a yeast protein, PTA1, that is a component of the yeast polyadenylation machinery. We show that multiple factors, including CstF, cleavage-polyadenylation specificity factor, and symplekin, can be isolated from cells as part of a large complex. These and other data suggest that symplekin may function in assembly of the polyadenylation machinery.