Supplemental feeding of wildlife is a common practice often undertaken for recreational or management purposes, but it may have unintended consequences for animal health. Understanding cryptic effects of diet supplementation on the gut microbiomes of wild mammals is important to inform conservation and management strategies. Multiple laboratory studies have demonstrated the importance of the gut microbiome for extracting and synthesizing nutrients, modulating host immunity, and many other vital host functions, but these relationships can be disrupted by dietary perturbation. The well-described interplay between diet, the microbiome, and host health in laboratory and human systems highlights the need to understand the consequences of supplemental feeding on the microbiomes of free-ranging animal populations. This study describes changes to the gut microbiomes of wild elk under different supplemental feeding regimes. We demonstrated significant cross-sectional variation between elk at different feeding locations and identified several relatively low-abundance bacterial genera that differed between fed versus unfed groups. In addition, we followed four of these populations through mid-season changes in supplemental feeding regimes and demonstrated a significant shift in microbiome composition in a single population that changed from natural forage to supplementation with alfalfa pellets. Some of the taxonomic shifts in this population mirrored changes associated with ruminal acidosis in domestic livestock. We discerned no significant changes in the population that shifted from natural forage to hay supplementation, or in the populations that changed from one type of hay to another. Our results suggest that supplementation with alfalfa pellets alters the native gut microbiome of elk, with potential implications for population health.