Replacement of coral by macroalgae in post-disturbance reefs, also called a “coral-macroalgal regime shift”, is increasing in response to climate-driven ocean warming. Such ecosystem change is known to impact planktonic and benthic reef microbial communities but few studies have examined the effect on animal microbiota. In order to understand the consequence of coral-macroalgal shifts on the coral reef fish enteric bacteriome, we used a metabarcoding approach to examine the gut bacteriomes of 99 individual fish representing 36 species collected on reefs of the Inner Seychelles islands that, following bleaching, had either recovered to coral domination, or shifted to macroalgae. While the coral-macroalgal shift did not influence the diversity, richness or variability of fish gut bacteriomes, we observed a significant effect on the composition (R2 = 0.02; p = 0.001), especially in herbivorous fishes (R2 = 0.07; p = 0.001). This change is accompanied by a significant increase in the proportion of fermentative bacteria (Rikenella, Akkermensia, Desulfovibrio, Brachyspira) and associated metabolisms (carbohydrates metabolism, DNA replication, and nitrogen metabolism) in relation to the strong turnover of Scarinae and Siganidae fishes. Predominance of fermentative metabolisms in fish found on macroalgal dominated reefs indicates that regime shifts not only affect the taxonomic composition of fish bacteriomes, but also have the potential to affect ecosystem functioning through microbial functions.