Histone mRNAs are rapidly degraded at the end of S phase or when DNA replication is inhibited. Histone mRNAs end in a conserved stem-loop rather than a poly(A) tail. Degradation of histone mRNAs requires the stem-loop sequence, which binds the stem-loop-binding protein (SLBP), active translation of the histone mRNA, and the location of the stem-loop close to the termination codon. We report that the initial step in histone mRNA degradation is the addition of uridines to the 3' end of the histone mRNA, both after inhibition of DNA replication and at the end of S phase. Lsm1 is required for histone mRNA degradation and is present in a complex containing SLBP on the 3' end of histone mRNA after inhibition of DNA replication. We cloned degradation intermediates that had been partially degraded from both the 5' and the 3' ends. RNAi experiments demonstrate that both the exosome and 5'-to-3' decay pathway components are required for degradation, and individual histone mRNAs are then degraded simultaneously 5' to 3' and 3' to 5'.