Innovative fish diets made of terrestrial plants supplemented with sustainable protein sources free of fish-derived proteins could contribute to reducing the environmental impact of the farmed fish industry. However, such alternative diets may influence fish gut microbial community, health, and, ultimately, growth performance. Here, we developed five fish feed formulas composed of terrestrial plant-based nutrients, in which fish-derived proteins were substituted with sustainable protein sources, including insect larvae, cyanobacteria, yeast, or recycled processed poultry protein. We then analyzed the growth performance of European sea bass (Dicentrarchus labrax L.) and the evolution of gut microbiota of fish fed the five formulations. We showed that replacement of 15% protein of a vegetal formulation by insect or yeast proteins led to a significantly higher fish growth performance and feed intake when compared with the full vegetal formulation, with feed conversion ratio similar to a commercial diet. 16S rRNA gene sequencing monitoring of the sea bass gut microbial community showed a predominance of Proteobacteria, Firmicutes, Actinobacteria, and Bacteroidetes phyla. The partial replacement of protein source in fish diets was not associated with significant differences on gut microbial richness. Overall, our study highlights the adaptability of European sea bass gut microbiota composition to changes in fish diet and identifies promising alternative protein sources for sustainable aquafeeds with terrestrial vegetal complements.