Poly(A)-specific ribonuclease (PARN) is a processive 3'-exoribonuclease involved in the decay of eukaryotic mRNAs. Interestingly, PARN interacts not only with the 3' end of the mRNA but also with its 5' end as PARN contains an RRM domain that specifically binds both the poly(A) tail and the 7-methylguanosine (m(7)G) cap. The interaction of PARN with the 5' cap of mRNAs stimulates the deadenylation activity and enhances the processivity of this reaction. We have determined the crystal structure of the PARN-RRM domain with a bound m(7)G triphosphate nucleotide, revealing a novel binding mode for the m(7)G cap. The structure of the m(7)G binding pocket is located outside of the canonical RNA-binding surface of the RRM domain and differs significantly from that of other m(7)G-cap-binding proteins. The crystal structure also shows a remarkable conformational flexibility of the RRM domain, leading to a perfect exchange of two alpha-helices with an adjacent protein molecule in the crystal lattice.