Environmental degradation has the potential to alter key mutualisms that underlie the structure and function of ecological communities. How microbial communities associated with fishes vary across populations and in relation to habitat characteristics remains largely unknown despite their fundamental roles in host nutrition and immunity. We find significant differences in the gut microbiome composition of a facultative coral-feeding butterflyfish (Chaetodon capistratus) across Caribbean reefs that differ markedly in live coral cover (∼0–30%). Fish gut microbiomes were significantly more variable at degraded reefs, a pattern driven by changes in the relative abundance of the most common taxa potentially associated with stress. We also demonstrate that fish gut microbiomes on severely degraded reefs have a lower abundance of Endozoicomonas and a higher diversity of anaerobic fermentative bacteria, which may suggest a less coral dominated diet. The observed shifts in fish gut bacterial communities across the habitat gradient extend to a small set of potentially beneficial host associated bacteria (i.e., the core microbiome) suggesting essential fish-microbiome interactions may be vulnerable to severe coral degradation.