Algivorous sea urchins like Tripneustes gratilla elatensis can obtain energy from a diet of a single algal species, which may result in consequent changes in their gut microbe assemblies and association networks. To ascertain whether specific microbes lead to such changes, we compared the microbial assembly in the three major gut regions of the sea urchin when fed a mono-specific algal diet of either Ulva fasciata, or Gracilaria conferta, or an algal-free diet. DNA extracts from at least 5 individuals from each diet treatment were used for Illumina MiSeq-based 16S rRNA gene sequencing (V3–V4 region). We calculated the niche breadth of each microbe in the assembly to identify core, generalist, specialist, or unique microbes. Network analyzers were used to measure the connectivity of the entire assembly, each microbe within it, and whether it altered with a given diet or gut region. Lastly, analysis of the metabolic arsenal of key microbes in the gut enabled us to understand their potential contribution to the decomposition of dietary algal polysaccharides. Sea urchins fed with U. fasciata grew faster, and their gut microbiome network was rich in bacterial associations (edges) and networking clusters. Bacteroidetes was the keystone microbe phylum in the gut, with core, generalist, and specialist representatives. A few microbes of this phylum were central hub nodes that maintained community connectivity, while others were driver microbes that led the rewiring of the assembly network based on diet type through changes in their associations and centrality. Niche breadth agreed with microbes’ richness in genes for carbohydrate-active enzymes and correlated Bacteroidetes specialists to the decomposition of specific polysaccharides in the algal diets. We propose our findings contribute to expanding the knowledge on the gut microbial assembly in T. gratilla elatensis while strengthening the correlation between microbes’ generalism or specialism in differed ecological niches and their metabolic arsenal, which may aid host nutrition.