The gut microbiota structure reflects both a host phylogenetic history and a signature of adaptation to the host ecological, mainly trophic niches. African cichlid fishes, with their array of closely related species that underwent a rapid dietary niche radiation, offer a particularly interesting system to explore the relative contribution of these two factors in nature. Here we surveyed the host intra- and interspecific natural variation of the gut microbiota of five cichlid species from the monophyletic tribe Perissodini of lake Tanganyika, whose members transitioned from being zooplanktivorous to feeding primarily on fish scales. The outgroup riverine species Astatotilapia burtoni, largely omnivorous, was also included in the study. Fusobacteria, Firmicutes and Proteobacteria represented the dominant components in the gut microbiota of all 30 specimens analysed according to two distinct 16S rRNA markers. All members of the Perissodini tribe showed a homogenous pattern of microbial alpha and beta diversities, with no significant qualitative differences, despite changes in diet. The recent diet shift between zooplantkon- and scale-eaters simply reflects on a significant enrichment of Clostridium taxa in scale-eaters where they might be involved in the scale metabolism. Comparison with the omnivorous species A. burtoni suggests that, with increased host phylogenetic distance and/or increasing herbivory, the gut microbiota begins differentiating also at qualitative level. The cichlids show presence of a large conserved core of taxa and a small set of core OTUs (average 13–15%), remarkably stable also in captivity, and putatively favoured by both restricted microbial transmission among related hosts (putatively enhanced by mouthbrooding behavior) and common host constraints. This study sets the basis for a future large-scale investigation of the gut microbiota of cichlids and its adaptation in the process of the host adaptive radiation.