Class I histone deacetylases (HDACs) repress transcription by deacetylating histones and have been shown to play crucial roles in mouse, Xenopus, zebrafish, and C. elegans development. To identify the molecular networks regulated by a class I HDAC in a multicellular organism, we carried out a global gene expression profiling study using C. elegans embryos, and identified tissue-specific and extracellular matrix (ECM)-related genes as major HDA-1 targets. Ectopic expression of HDA-1 or C. elegans cystatin, an HDA-1 target identified from the microarray, significantly perturbed mammalian cell invasion. Similarly, RNAi depletion or overexpression of human HDAC-1 also affected cell migration. These findings suggest that HDA-1/HDAC-1 may play a critical, evolutionarily conserved role in regulating the extracellular microenvironment. Because human HDACs are targets for cancer therapy, these findings have significant implications in cancer treatment.