Animal gut microbiomes are critical to host physiology and fitness. The gut microbiomes of fishes-the most abundant and diverse vertebrate clade-have received little attention relative to other clades. Coral reef fishes, in particular, make up a wide range of evolutionary histories and feeding ecologies that are likely associated with gut microbiome diversity. The repeated evolution of herbivory in fishes and mammals also allows us to examine microbiome similarity in relationship to diet across the entire vertebrate tree of life. Here, we generate a large coral reef fish gut microbiome dataset (n = 499 samples, 19 species) and combine it with a diverse aggregation of public microbiome data (n = 447) to show that host diet drives significant convergence between coral reef fish and mammalian gut microbiomes. We demonstrate that this similarity is largely driven by carnivory and herbivory and that herbivorous and carnivorous hosts exhibit distinct microbial compositions across fish and mammals. We also show that fish and mammal gut microbiomes share prominent microbial taxa, including Ruminoccocus spp. and Akkermansia spp., and predicted metabolic pathways. Despite the major evolutionary and ecological differences between fishes and mammals, our results reveal that their gut microbiomes undergo similar dietary selective pressures. Thus, diet, in addition to phylosymbiosis must be considered even when comparing the gut microbiomes of distantly related hosts.