Changes in the intestinal microbiota have been associated with development and progression of colorectal cancer (CRC). Archaea are stable components of the microbiota, but little is known about their composition or contribution to colorectal carcinogenesis. We analyzed archaea in fecal microbiomes of 2 large cohorts of patients with CRC.We performed shotgun metagenomic analyses of fecal samples from 585 subjects (184 patients with CRC, 197 patients with adenomas, and 204 healthy individuals [controls]) from discovery (165 individuals) and validation (420 individuals) cohorts. Assignment of taxonomies was performed by exact k-mer alignment against an integrated microbial reference genome database.Principal component analysis of archaeomes revealed distinct clusters in fecal samples from patients with CRC, patients with adenomas, and controls (P<.001), indicating an alteration in the composition of enteric archaea during tumorigenesis. Fecal samples from patients with CRC had significant enrichment of halophilic and depletion of methanogenic archaea. The halophilic Natrinema sp. J7-2 increased progressively in samples from controls, to patients with adenomas, to patients with CRC. Abundances of 9 archaea species that were enriched in fecal samples from patients with CRC distinguished them from controls with areas under the receiver operating characteristic curve of 0.82 in the discovery cohort and 0.83 in the validation cohort. An association between archaea and bacteria diversities was observed in fecal samples from controls but not from patients with CRC. Archaea that were enriched in fecal samples from patients with CRC had an extensive mutual association with bacteria that were enriched in the same samples, and exclusivity with bacteria that were lost from these samples.Archaeomes of fecal samples from patients with CRC are characterized by enrichment of halophiles and depletion of methanogens. Studies are needed to determine whether associations between specific archaea and bacteria species in samples from patients with CRC contribute to or are a response to colorectal tumorigenesis.