Chromatin modification genes play crucial roles in development and disease. In Caenorhabditis elegans, the class I histone deacetylase family member hda-1, a component of the nucleosome remodeling and deacetylation complex, has been shown to control cell proliferation. We recovered hda-1 in an RNA interference screen for genes involved in the morphogenesis of the egg-laying system. We found that hda-1 mutants have abnormal vulva morphology and vulval-uterine connections (i.e., no uterine-seam cell). We characterized the vulval defects by using cell fate-specific markers and found that hda-1 is necessary for the specification of all seven vulval cell types. The analysis of the vulval-uterine connection defect revealed that hda-1 is required for the differentiation of the gonadal anchor cell (AC), which in turn induces ventral uterine granddaughters to adopt π fates, leading to the formation of the uterine-seam cell. Consistent with these results, hda-1 is expressed in the vulva and AC. A search for hda-1 target genes revealed that fos-1 (fos proto-oncogene family) acts downstream of hda-1 in vulval cells, whereas egl-43 (evi1 proto-oncogene family) and nhr-67 (tailless homolog, NHR family) mediate hda-1 function in the AC. Furthermore, we showed that AC expression of hda-1 plays a crucial role in the regulation of the lin-12/Notch ligand lag-2 to specify π cell fates. These results demonstrate the pivotal role of hda-1 in the formation of the vulva and the vulval-uterine connection. Given that hda-1 homologs are conserved across the phyla, our findings are likely to provide a better understanding of HDAC1 function in development and disease.