The exosome complex of 3'-5' exonucleases participates in RNA maturation and quality control and can rapidly degrade RNA-protein complexes in vivo. However, the purified exosome showed weak in vitro activity, indicating that rapid RNA degradation requires activating cofactors. This work identifies a nuclear polyadenylation complex containing a known exosome cofactor, the RNA helicase Mtr4p; a poly(A) polymerase, Trf4p; and a zinc knuckle protein, Air2p. In vitro, the Trf4p/Air2p/Mtr4p polyadenylation complex (TRAMP) showed distributive RNA polyadenylation activity. The presence of the exosome suppressed poly(A) tail addition, while TRAMP stimulated exosome degradation through structured RNA substrates. In vivo analyses showed that TRAMP is required for polyadenylation and degradation of rRNA and snoRNA precursors that are characterized exosome substrates. Poly(A) tails stimulate RNA degradation in bacteria, suggesting that this is their ancestral function. We speculate that this function was maintained in eukaryotic nuclei, while cytoplasmic mRNA poly(A) tails acquired different roles in translation.