Gut microbial dysbiosis contributes to the development of colorectal cancer (CRC). Here we catalogue the microbial communities in human gut mucosae at different stages of colorectal tumorigenesis. We analyse the gut mucosal microbiome of 47 paired samples of adenoma and adenoma-adjacent mucosae, 52 paired samples of carcinoma and carcinoma-adjacent mucosae and 61 healthy controls. Probabilistic partitioning of relative abundance profiles reveals that a metacommunity predominated by members of the oral microbiome is primarily associated with CRC. Analysis of paired samples shows differences in community configurations between lesions and the adjacent mucosae. Correlations of bacterial taxa indicate early signs of dysbiosis in adenoma, and co-exclusive relationships are subsequently more common in cancer. We validate these alterations in CRC-associated microbiome by comparison with two previously published data sets. Our results suggest that a taxonomically defined microbial consortium is implicated in the development of CRC.