Altered microbiome composition and aberrant promoter hypermethylation of tumor suppressor genes (TSGs) are two important hallmarks of colorectal cancer (CRC). Here we performed concurrent 16S rRNA gene sequencing and methyl-CpG binding domain-based capture sequencing in 33 tissue biopsies (5 normal colonic mucosa tissues, 4 pairs of adenoma and adenoma-adjacent tissues, and 10 pairs of CRC and CRC-adjacent tissues) to identify significant associations between TSG promoter hypermethylation and CRC-associated bacteria, followed by functional validation of the methylation-associated bacteria. Fusobacterium nucleatum and Hungatella hathewayi were identified as the top two methylation-regulating bacteria. Targeted analysis on bona fide TSGs revealed that H. hathewayi and Streptococcus spp. significantly correlated with CDX2 and MLH1 promoter hypermethylation, respectively. Mechanistic validation with cell-line and animal models revealed that F. nucleatum and H. hathewayi upregulated DNA methyltransferase. H. hathewayi inoculation also promoted colonic epithelial cell proliferation in germ-free and conventional mice. Our integrative analysis revealed previously unknown epigenetic regulation of TSGs in host cells through inducing DNA methyltransferase by F. nucleatum and H. hathewayi, and established the latter as CRC-promoting bacteria. Video abstract.