Host gut microbiomes play an important role in animal health and resilience to conditions, such as malnutrition and starvation. These host-microbiome relationships are poorly understood in the marine mussel Perna canaliculus, which experiences significant variations in food quantity and quality in coastal areas. Prolonged starvation may be a contributory factor towards incidences of mass mortalities in farmed mussel populations, resulting in highly variable production costs and unreliable market supplies. Here, we examine the gut microbiota of P. canaliculus in response to starvation and subsequent re-feeding using high-throughput amplicon sequencing of the 16S rRNA gene. Mussels showed no change in bacterial species richness when subjected to a 14-day starvation, followed by re-feeding/recovery. However, beta bacteria diversity revealed significant shifts (PERMANOVA p-value < 0.001) in community structure in the starvation group and no differences in the subsequent recovery group (compared to the control group) once they were re-fed, highlighting their recovery capability and resilience. Phylum-level community profiles revealed an elevation in dominance of Proteobacteria (ANCOM-BC p-value <0.001) and Bacteroidota (ANCOM-BC p-value = 0.04) and lower relative abundance of Cyanobacteria (ANCOM-BC p-value = 0.01) in the starvation group compared to control and recovery groups. The most abundant genus-level shifts revealed relative increases of the heterotroph Halioglobus (p-value < 0.05) and lowered abundances of the autotroph Synechococcus CC9902 in the starvation group. Furthermore, a SparCC correlation network identified co-occurrence of a cluster of genera with elevated relative abundance in the starved mussels that were positively correlated with Synechococcus CC9902. The findings from this work provide the first insights into the effect of starvation on the resilience capacity of Perna canaliculus gut microbiota, which is of central importance to understanding the effect of food variation and limitation in farmed mussels.