The incidence of colorectal cancer (CRC) has increased worldwide, and early diagnosis is crucial to reduce mortality rates. Therefore, new noninvasive biomarkers for CRC are required. Recent studies have revealed an imbalance in the oral and gut microbiomes of patients with CRC, as well as impaired gut vascular barrier function. In the present study, the microbiomes of saliva, crevicular fluid, feces, and non-neoplastic and tumor intestinal tissue samples of 93 CRC patients and 30 healthy individuals without digestive disorders (non-CRC) were analyzed by 16S rRNA metabarcoding procedures. The data revealed that Parvimonas, Fusobacterium, and Bacteroides fragilis were significantly over-represented in stool samples of CRC patients, whereas Faecalibacterium and Blautia were significantly over-abundant in the non-CRC group. Moreover, the tumor samples were enriched in well-known periodontal anaerobes, including Fusobacterium, Parvimonas, Peptostreptococcus, Porphyromonas, and Prevotella. Co-occurrence patterns of these oral microorganisms were observed in the subgingival pocket and in the tumor tissues of CRC patients, where they also correlated with other gut microbes, such as Hungatella. This study provides new evidence that oral pathobionts, normally located in subgingival pockets, can migrate to the colon and probably aggregate with aerobic bacteria, forming synergistic consortia. Furthermore, we suggest that the group composed of Fusobacterium, Parvimonas, Bacteroides, and Faecalibacterium could be used to design an excellent noninvasive fecal test for the early diagnosis of CRC. The combination of these four genera would significantly improve the reliability of a discriminatory test with respect to others that use a single species as a unique CRC biomarker.