Oculopharyngeal muscular dystrophy (OPMD), a late-onset disorder characterized by progressive degeneration of specific muscles, results from the extension of a polyalanine tract in poly(A) binding protein nuclear 1 (PABPN1). While the roles of PABPN1 in nuclear polyadenylation and regulation of alternative poly(A) site choice are established, the molecular mechanisms behind OPMD remain undetermined. Here, we show, using Drosophila and mouse models, that OPMD pathogenesis depends on affected poly(A) tail lengths of specific mRNAs. We identify a set of mRNAs encoding mitochondrial proteins that are down-regulated starting at the earliest stages of OPMD progression. The down-regulation of these mRNAs correlates with their shortened poly(A) tails and partial rescue of their levels when deadenylation is genetically reduced improves muscle function. Genetic analysis of candidate genes encoding RNA binding proteins using the Drosophila OPMD model uncovers a potential role of a number of them. We focus on the deadenylation regulator Smaug and show that it is expressed in adult muscles and specifically binds to the down-regulated mRNAs. In addition, the first step of the cleavage and polyadenylation reaction, mRNA cleavage, is affected in muscles expressing alanine-expanded PABPN1. We propose that impaired cleavage during nuclear cleavage/polyadenylation is an early defect in OPMD. This defect followed by active deadenylation of specific mRNAs, involving Smaug and the CCR4-NOT deadenylation complex, leads to their destabilization and mitochondrial dysfunction. These results broaden our understanding of the role of mRNA regulation in pathologies and might help to understand the molecular mechanisms underlying neurodegenerative disorders that involve mitochondrial dysfunction.