Due to technical limitations, most gut microbiome studies have focused on prokaryotes, overlooking viruses. Phanta, a virome-inclusive gut microbiome profiling tool, overcomes limitations of assembly-based viral profiling methods by using customized k-mer-based classification tools and incorporating recently published catalogs of gut viral genomes. Phanta’s optimizations consider the small genome size of viruses, sequence homology with prokaryotes, and interactions with other gut microbes. Extensive testing of Phanta on simulated data demonstrates that it quickly and accurately quantifies prokaryotes and viruses. When applied to 245 fecal metagenomes from healthy adults, Phanta identifies ~200 viral species per sample, ~5x more than standard assembly-based methods. We observe a ~2:1 ratio between DNA viruses and bacteria, with higher inter-individual variability of the gut virome compared to the gut bacteriome. In another cohort, we observe that Phanta performs equally well on bulk vs. virus-enriched metagenomes, making it possible to study prokaryotes and viruses in a single experiment, with a single analysis.