Variation in the composition of microorganisms in the rumen (the rumen microbiome) of dairy cattle (Bos taurus) is of great interest because of possible links to methane emission levels. Feed additives are one method being investigated to reduce enteric methane production by dairy cattle. Here we report the effect of 2 methane-mitigating feed additives (grapemarc and a combination of lipids and tannin) on rumen microbiome profiles of Holstein dairy cattle. We used untargeted (shotgun) massively parallel sequencing of microbes present in rumen fluid to generate quantitative rumen microbiome profiles. We observed large effects of the feed additives on the rumen microbiome profiles using multiple approaches, including linear mixed modeling, hierarchical clustering, and metagenomic predictions. The effect on the fecal microbiome profiles was not detectable using hierarchical clustering, but was significant in the linear mixed model and when metagenomic predictions were used, suggesting a more subtle effect of the diets on the lower gastrointestinal microbiome. A differential representation analysis (analogous to differential expression in RNA sequencing) showed significant overlap in the contigs (which are genome fragments representing different microorganism species) that were differentially represented between experiments. These similarities suggest that, despite the different additives used, the 2 diets assessed in this investigation altered the microbiomes of the samples in similar ways. Contigs that were differentially represented in both experiments were tested for associations with methane production in an independent set of animals. These animals were not treated with a methane-mitigating diet, but did show substantial natural variation in methane emission levels. The contigs that were significantly differentially represented in response to both dietary additives showed a significant enrichment for associations with methane production. This suggests that these methane-mitigating diets have altered the rumen microbiome toward naturally low methane-emitting microbial profiles. The contig sequences are predominantly new and include Faecalibacterium spp. The contigs we have identified here are potential biomarkers for low-methane-emitting cattle.