We have used an in vitro system that reproduces in vivo aspects of mRNA turnover to elucidate mechanisms of deadenylation. DAN, the major enzyme responsible for poly(A) tail shortening in vitro, specifically interacts with the 5' cap structure of RNA substrates, and this interaction is greatly stimulated by a poly(A) tail. Several observations suggest that cap-DAN interactions are functionally important for the networking between regulated mRNA stability and translation. First, uncapped RNA substrates are inefficiently deadenylated. Second, a stem-loop structure in the 5' UTR dramatically reduces deadenylation by interfering with cap-DAN interactions. Third, the addition of cap binding protein eIF4E inhibits deadenylation in vitro. These data provide insights into the early steps of substrate recognition that target an mRNA for degradation.