Accumulating evidence has related the gut microbiota to colorectal cancer (CRC). Fusobacterium nucleatum has repeatedly been linked to colorectal tumorigenesis. The aim of this study was to investigate microbial composition in different sampling sites, in order to profile the microbial dynamics with CRC progression. Further, we characterized the tumor-associated F. nucleatum subspecies. Here, we conducted Illumina Miseq next-generation sequencing of the 16S rRNA V4 region in biopsy samples, to investigate microbiota alterations in cancer patients, patients with adenomatous polyp, and healthy controls in Norway. Further, Fusobacterium positive tumor biopsies were subjected to MinION nanopore sequencing of Fusobacterium-specific amplicons to characterize the Fusobacterium species and subspecies. We found enrichment of oral biofilm-associated bacteria, Fusobacterium, Gemella, Parvimonas, Granulicatella, Leptotrichia, Peptostreptococcus, Campylobacter, Selenomonas, Porphyromonas, and Prevotella in cancer patients compared to adenomatous polyp patients and control patients. Higher abundance of amplicon sequence variants (ASVs) classified as Phascolarctobacterium, Bacteroides vulgatus, Bacteroides plebeius, Bacteroides eggerthii, Tyzzerella, Desulfovibrio, Frisingicoccus, Eubacterium coprostanoligenes group, and Lachnospiraceae were identified in cancer and adenomatous polyp patients compared to healthy controls. F. nucleatum ssp. animalis was the dominating subspecies. F. nucleatum ssp. nucleatum, F. nucleatum ssp. vincentii, Fusobacterium pseudoperiodonticum, Fusobacterium necrophorum, and Fusobacterium gonidiaformans were identified in five samples. Several biofilm-associated bacteria were enriched at multiple sites in cancer patients. Another group of bacteria was enriched in both cancer and polyps, suggesting that they may have a role in polyp development and possibly early stages of CRC.