The lifespan of most eukaryotic mRNAs is modulated by the gradual shortening of the poly(A) tail and removal of the associated poly(A)-binding protein. The human PAN2-PAN3 complex catalyzes initial deadenylation by shortening long poly(A) tails associated with PABPC1. Both PAN2-PAN3 and PABPC1 are evolutionarily conserved from fungi to humans. How the human complex has adapted to recognize and act on longer poly(A) tails characteristic of mammalian mRNAs remains unclear. Here, we report a method to obtain homo-polymeric poly(A) RNAs up to 240 nt, mimicking the synthesis length of poly(A) tails in mammals. We recapitulate human deadenylation properties in vitro, with PAN2-PAN3 showing greater activity on long poly(A)-PABPC1 ribonucleoprotein substrates. Single-particle cryo-electron microscopy (cryo-EM) analyses of PAN2-PAN3 bound to poly(A)-PABPC1 ribonucleoproteins uncover a longer substrate-binding path in the case of the human deadenylase compared to fungi. Altogether, these data provide a rationale for the co-evolution of deadenylase properties and poly(A) tail lengths.