The degradation of the poly(A) tail is crucial for posttranscriptional gene regulation and for quality control of mRNA. Poly(A)-specific ribonuclease (PARN) is one of the major mammalian 3' specific exo-ribonucleases involved in the degradation of the mRNA poly(A) tail, and it is also involved in the regulation of translation in early embryonic development. The interaction between PARN and the m(7)GpppG cap of mRNA plays a key role in stimulating the rate of deadenylation. Here we report the solution structures of the cap-binding domain of mouse PARN with and without the m(7)GpppG cap analog. The structure of the cap-binding domain adopts the RNA recognition motif (RRM) with a characteristic alpha-helical extension at its C-terminus, which covers the beta-sheet surface (hereafter referred to as PARN RRM). In the complex structure of PARN RRM with the cap analog, the base of the N(7)-methyl guanosine (m(7)G) of the cap analog stacks with the solvent-exposed aromatic side chain of the distinctive tryptophan residue 468, located at the C-terminal end of the second beta-strand. These unique structural features in PARN RRM reveal a novel cap-binding mode, which is distinct from the nucleotide recognition mode of the canonical RRM domains.