The poly(A) tail shortening in mRNA, called deadenylation, is the first rate-limiting step in eukaryotic mRNA turnover, and the polyadenylate-binding protein (PABP) appears to be involved in the regulation of this step. However, the precise role of PABP remains largely unknown in higher eukaryotes. Here we identified and characterized a human PABP-dependent poly(A) nuclease (hPAN) complex consisting of catalytic hPan2 and regulatory hPan3 subunits. hPan2 has intrinsically a 3' to 5' exoribonuclease activity and requires Mg2+ for the enzyme activity. On the other hand, hPan3 interacts with PABP to simulate hPan2 nuclease activity. Interestingly, the hPAN nuclease complex has a higher substrate specificity to poly(A) RNA upon its association with PABP. Consistent with the roles of hPan2 and hPan3 in mRNA decay, the two subunits exhibit cytoplasmic co-localization. Thus, the human PAN complex is a poly(A)-specific exoribonuclease that is stimulated by PABP in the cytoplasm.