Machado-Joseph disease (MJD), the most common dominantly inherited ataxia worldwide, is caused by a polyglutamine (polyQ) expansion in the deubiquitinating (DUB) enzyme ataxin-3. Interestingly, MJD can present clinically with features of Parkinsonism. In this study, we identify parkin, an E3 ubiquitin-ligase responsible for a common familial form of Parkinson's disease, as a novel ataxin-3 binding partner. The interaction between ataxin-3 and parkin is direct, involves multiple domains and is greatly enhanced by parkin self-ubiquitination. Moreover, ataxin-3 deubiquitinates parkin directly in vitro and in cells. Compared with wild-type ataxin-3, MJD-linked polyQ-expanded mutant ataxin-3 is more active, possibly owing to its greater efficiency at DUB K27- and K29-linked Ub conjugates on parkin. Remarkably, mutant but not wild-type ataxin-3 promotes the clearance of parkin via the autophagy pathway. The finding is consistent with the reduction in parkin levels observed in the brains of transgenic mice over-expressing polyQ-expanded but not wild-type ataxin-3, raising the intriguing possibility that increased turnover of parkin may contribute to the pathogenesis of MJD and help explain some of its parkinsonian features.