N-Myc oncoprotein induces neuroblastoma, which arises from undifferentiated neuroblasts in the sympathetic system, by modulating gene and protein expression and consequently causing cell differentiation block and cell proliferation. The class IIa histone deacetylase HDAC5 represses gene transcription, and blocks myoblast, osteoblast and leukemia cell differentiation. Here we showed that N-Myc up-regulated HDAC5 expression in neuroblastoma cells. Conversely, HDAC5 repressed the ubiquitin-protein ligase NEDD4 gene expression, increased Aurora A gene expression, and consequently up-regulated N-Myc protein expression. Genome-wide gene expression analysis and protein co-immunoprecipitation assays revealed that HDAC5 and N-Myc commonly repressed the expression of a subset of genes by forming a protein complex, while HDAC5 and the class III histone deacetylase SIRT2 commonly, but independently, repressed the expression of another subset of genes. Moreover, HDAC5 blocked cell differentiation and induced cell proliferation. Taken together, our data identify HDAC5 as a novel important co-factor in N-Myc oncogenesis, and provide the critical evidence for the potential application of HDAC5 inhibitors for the therapy of N-Myc-induced neuroblastoma and potentially c-Myc-induced other malignancies.