The CFP1 CXXC zinc finger protein targets the SET1/COMPASS complex to non-methylated CpG rich promoters to implement tri-methylation of histone H3 Lys4 (H3K4me3). Although H3K4me3 is widely associated with gene expression, the effects of CFP1 loss vary, suggesting additional chromatin factors contribute to context dependent effects. Using a proteomics approach, we identified CFP1 associated proteins and an unexpected direct link between Caenorhabditis elegans CFP-1 and an Rpd3/Sin3 small (SIN3S) histone deacetylase complex. Supporting a functional connection, we find that mutants of COMPASS and SIN3 complex components genetically interact and have similar phenotypic defects including misregulation of common genes. CFP-1 directly binds SIN-3 through a region including the conserved PAH1 domain and recruits SIN-3 and the HDA-1/HDAC subunit to H3K4me3 enriched promoters. Our results reveal a novel role for CFP-1 in mediating interaction between SET1/COMPASS and a Sin3S HDAC complex at promoters.