The transcriptional co-repressor CtBP (C-terminal binding protein) is implicated in tumorigenesis because it is targeted by the adenovirus E1A protein during oncogenic transformation. Genetic studies have also identified a crucial function for CtBP in animal development. CtBP is recruited to DNA by transcription factors that contain a PXDLS motif, but the detailed molecular events after the recruitment of CtBP to DNA and the mechanism of CtBP function in tumorigenesis are largely unknown. Here we report the identification of a CtBP complex that contains the essential components for both gene targeting and coordinated histone modifications, allowing for the effective repression of genes targeted by CtBP. Inhibiting the expression of CtBP and its associated histone-modifying activities by RNA-mediated interference resulted in alterations of histone modifications at the promoter of the tumour invasion suppressor gene E-cadherin and increased promoter activity in a reporter assay. These findings identify a molecular mechanism by which CtBP mediates transcriptional repression and provide insight into CtBP participation in oncogenesis.