Histone H3K4 methylation has been linked to transcriptional activation. KDM5A (also known as RBP2 or JARID1A), a member of the KDM5 protein family, is an H3K4 demethylase, previously implicated in the regulation of transcription and differentiation. Here, we show that KDM5A is physically and functionally associated with two histone deacetylase complexes. Immunoaffinity purification of KDM5A confirmed a previously described association with the SIN3B-containing histone deacetylase complex and revealed an association with the nucleosome remodeling and deacetylase (NuRD) complex. Sucrose density gradient and sequential immunoprecipitation analyses further confirmed the stable association of KDM5A with these two histone deacetylase complexes. KDM5A depletion led to changes in the expression of hundreds of genes, two-thirds of which were also controlled by CHD4, the NuRD catalytic subunit. Gene ontology analysis confirmed that the genes commonly regulated by both KDM5A and CHD4 were categorized as developmentally regulated genes. ChIP analyses suggested that CHD4 modulates H3K4 methylation levels at the promoter and coding regions of target genes. We further demonstrated that the Caenorhabditis elegans homologues of KDM5 and CHD4 function in the same pathway during vulva development. These results suggest that KDM5A and the NuRD complex cooperatively function to control developmentally regulated genes.