Associations between the gut microbiome and colorectal cancer (CRC) have been uncovered, but larger and more diverse studies are needed to assess their potential clinical use. We expanded upon 12 metagenomic datasets of patients with CRC (n = 930), adenomas (n = 210) and healthy control individuals (n = 976; total n = 2,116) with 6 new cohorts (n = 1,625) providing granular information on cancer stage and the anatomic location of tumors. We improved CRC prediction accuracy based solely on gut metagenomics (average area under the curve = 0.85) and highlighted the contribution of 19 newly profiled species and distinct Fusobacterium nucleatum clades. Specific gut species distinguish left-sided versus right-sided CRC (area under the curve = 0.66) with an enrichment of oral-typical microbes. We identified strain-specific CRC signatures with the commensal Ruminococcus bicirculans and Faecalibacterium prausnitzii showing subclades associated with late-stage CRC. Our analysis confirms that the microbiome can be a clinical target for CRC screening and characterizes it as a biomarker for CRC progression.