Poly(A)-specific ribonuclease (PARN) is a homodimeric, processive, and cap-interacting 3' exoribonuclease that efficiently degrades eukaryotic mRNA poly(A) tails. The crystal structure of a C-terminally truncated PARN in complex with m(7)GpppG reveals that, in one subunit, m(7)GpppG binds to a cavity formed by the RRM domain and the nuclease domain, whereas in the other subunit, it binds almost exclusively to the RRM domain. Importantly, our structural and competition data show that the cap-binding site overlaps with the active site in the nuclease domain. Mutational analysis demonstrates that residues involved in m(7)G recognition are crucial for cap-stimulated deadenylation activity, and those involved in both cap and poly(A) binding are important for catalysis. A modeled PARN, which shows that the RRM domain from one subunit and the R3H domain from the other subunit enclose the active site, provides a structural foundation for further studies to elucidate the mechanism of PARN-mediated deadenylation.