The translation of mammalian messenger RNAs (mRNAs) can be driven by either cap-binding proteins 80 and 20 (CBP80/20) or eukaryotic translation initiation factor (eIF)4E. Although CBP80/20-dependent translation (CT) is known to be coupled to an mRNA surveillance mechanism termed nonsense-mediated mRNA decay (NMD), its molecular mechanism and biological role remain obscure. Here, using a yeast two-hybrid screening system, we identify a stem-loop binding protein (SLBP) that binds to a stem-loop structure at the 3'-end of the replication-dependent histone mRNA as a CT initiation factor (CTIF)-interacting protein. SLBP preferentially associates with the CT complex of histone mRNAs, but not with the eIF4E-depedent translation (ET) complex. Several lines of evidence indicate that rapid degradation of histone mRNA on the inhibition of DNA replication largely takes place during CT and not ET, which has been previously unappreciated. Furthermore, the ratio of CBP80/20-bound histone mRNA to eIF4E-bound histone mRNA is larger than the ratio of CBP80/20-bound polyadenylated β-actin or eEF2 mRNA to eIF4E-bound polyadenylated β-actin or eEF2 mRNA, respectively. The collective findings suggest that mRNAs harboring a different 3'-end use a different mechanism of translation initiation, expanding the repertoire of CT as a step for determining the fate of histone mRNAs.