To perform the first concurrent characterization of gut and respiratory microbiome profiles in colorectal cancer patients from Western Siberia, Russia. We analyzed synchronous fecal and sputum samples from 40 treatment-naive colorectal cancer patients and 45 healthy controls using 16S rRNA gene (V3-V4) sequencing and QIIME 2-based bioinformatic workflows. While alpha-diversity indices did not differ significantly between groups, beta-diversity analysis revealed substantial compositional differences for both ecosystems. Colorectal cancer patients exhibited gut enrichment of Proteobacteria, Fusobacteria, Fusobacterium, Odoribacter, Lachnospiraceae_UCG-010, Erysipelatoclostridium, Parvimonas, Finegoldia, Clostridium and Bacteroides (Bacteroides fragilis), alongside sputum enrichment of phyla Bacteroidetes and Actinobacteria, as well as genera Neisseria, Prevotella, Lactobacillus, Rothia, Nocardia, Leptotrichia, Campylobacter, and Helicobacter. Stage-associated shifts included elevated Akkermansia in gut microbiomes of patients with advanced-stage disease and higher Campylobacter in early-stage sputum. These findings identify distinct gut–respiratory dysbiotic signatures in a previously understudied population. Our results underscore the potential of dual-compartment microbiome profiling for developing non-invasive biomarkers and require validation in larger, multicenter cohorts to elucidate mechanistic links between respiratory dysbiosis and colorectal carcinogenesis.