Machado-Joseph disease (MJD/SCA3) is an autosomal dominant neurodegenerative disease caused by the expansion of a CAG tract in the coding portion of the ATXN3 gene. The presence of ubiquitin-positive aggregates of the defective protein in affected neurons is characteristic of this and most of the polyglutamine disorders. Recently, the accumulation of the neural precursor cell expressed developmentally downregulated 8 (NEDD8), a ubiquitin-like protein, in the inclusions of MJD brains was reported. Here, we report a new molecular interaction between wild-type ataxin-3 and NEDD8, using in vitro and in situ approaches. Furthermore, we show that this interaction is not dependent on the ubiquitin-interacting motifs in ataxin-3, since the presence of the Josephin domain is sufficient for the interaction to occur. The conservation of the interaction between the Caenorhabditis elegans ataxin-3 homologue (atx-3) and NEDD8 suggests its biological and functional relevance. Molecular docking studies of the NEDD8 molecule to the Josephin domain of ataxin-3 suggest that NEDD8 interacts with ataxin-3 in a substrate-like mode. In agreement, ataxin-3 displays deneddylase activity against a fluorogenic NEDD8 substrate.