Malnutrition remains a major health problem in low- and middle-income countries. During low protein intake, <0.67 g/kg/day, there is a loss of nitrogen (N2 ) balance, due to the unavailability of amino acid for metabolism and unbalanced protein catabolism results. However, there are individuals, who consume the same low protein intake, and preserve N2 balance for unknown reasons. A novel factor, the gut microbiota, may account for these N2 balance differences. To investigate this, we correlated gut microbial profiles with the growth of four murine strains (C57Bl6/J, CD-1, FVB, and NIH-Swiss) on protein deficient (PD) diet. Results show that a PD diet exerts a strain-dependent impact on growth and N2 balance as determined through analysis of urinary urea, ammonia and creatinine excretion. Bacterial alpha diversity was significantly (P < 0.05, FDR) lower across all strains on a PD diet compared to normal chow (NC). Multi-group analyses of the composition of microbiomes (ANCOM) revealed significantly differential microbial signatures between the four strains independent of diet. However, mice on a PD diet demonstrated differential enrichment of bacterial genera including, Allobaculum (C57Bl6/J), Parabacteroides (CD-1), Turicibacter (FVB), and Mucispirillum (NIH-Swiss) relative to NC. For instance, selective comparison of the CD-1 (gained weight) and C57Bl6/J (did not gain weight) strains on PD diet also demonstrated significant pathway enrichment of dihydroorodate dehydrogenase, rRNA methyltransferases, and RNA splicing ligase in the CD-1 strains compared to C57Bl6/J strains; which might account in their ability to retain growth despite a protein deficient diet. Taken together, these results suggest a potential relationship between the specific gut microbiota, N2 balance and animal response to malnutrition.