Poly(A)-specific ribonuclease (PARN) and target of EGR1 protein 1 (TOE1) are nuclear granule-associated deadenylases, whose mutations are linked to multiple human diseases. Here, we applied mTAIL-seq and RNA sequencing (RNA-seq) to systematically identify the substrates of PARN and TOE1 and elucidate their molecular functions. We found that PARN and TOE1 do not modulate the length of mRNA poly(A) tails. Rather, they promote the maturation of nuclear small non-coding RNAs (ncRNAs). PARN and TOE1 act redundantly on some ncRNAs, most prominently small Cajal body-specific RNAs (scaRNAs). scaRNAs are strongly downregulated when PARN and TOE1 are compromised together, leading to defects in small nuclear RNA (snRNA) pseudouridylation. They also function redundantly in the biogenesis of telomerase RNA component (TERC), which shares sequence motifs found in H/ACA box scaRNAs. Our findings extend the knowledge of nuclear ncRNA biogenesis, and they provide insights into the pathology of PARN/TOE1-associated genetic disorders whose therapeutic treatments are currently unavailable.