The human gut virome, comprising diverse viruses including bacteriophages, plays a pivotal role in shaping microbial community dynamics and thus influencing host health. While bacterial components of the microbiome in colorectal cancer (CRC) have been extensively characterized, viral populations remain primarily unexplored, particularly in regard to their interactions with gut bacteria and relevance to the progression along the adenoma-carcinoma sequence.  In this study, we systematically analyzed viral abundance profiles with BAQLAVa on five publicly available gut metagenomic studies from around the world (n= 1432), including healthy, adenoma, and CRC-associated samples. We identified significant shifts in the composition of the gut viral profiles with CRC status and stage, as well as age, BMI and gender (p-value < 0.01). Further, several taxa were significantly associated with either CRC status or stage, including Buchavirus and several currently unannotated viruses. The majority of associations (63/65) associations were within the viral “dark matter”, suggestive of the overwhelming need to further study gut phages. Furthermore, annotation of host sources enabled classification of viruses as eukaryotic or prokaryotic suggests that, while BAQLaVa incorporates eukaryotic taxa into it’s database, few were identified in real data. Taken together these results point to CRC metagenomes harboring vast and understudied viral phages. Correlating viral and bacterial abundance, using HAllA, we identify frequently associated bacterial-viral pairs, like E. coli with Lambdavirus and Xuanwuvirus, and F. prausnitzii with Toutatisvirus. This also naively predicted host – phage relationships for many common gut commensals and CRC-associated taxa. Comparative analysis between CRC datasets and the HMP2, revealed conserved viral-bacterial interaction networks, with specific phage genome bins recurrently linked to CRC-associated bacterial species such as Fusobacterium nucleatum. This analysis underscores the significance of gut viruses as potential associates of dysbiosis and disease in CRC. Our findings provide a foundation for future functional studies of gut virome contributions to microbial ecology and host-pathogen interactions.