The tight association between malnutrition and gut microbiota (GM) dysbiosis enables microbiota-targeting intervention to be a promising strategy. Thus, we used a malnourished pig model to investigate the host response and GM alterations under different diet supplementation strategies. Pigs at age of 4 weeks were fed with pure maize diet to induce malnutrition symptoms, and followed by continuous feeding with maize (Maize, n = 8) or refeeding using either corn-soy-blend (CSB+, n = 10) or millet-soy-blend based (MSB+, n = 10) supplementary food for 3 weeks. Meanwhile, 8 pigs were fed on a standard formulated ration as control (Ref). The effect of nutritional supplementation was assessed by the growth status, blood chemistry, gastrointestinal pathology, mucosal microbiota composition and colon production of short-chain fatty acids. Compared with purely maize-fed pigs, both CSB + and MSB+ elevated the concentrations of total protein and globulin in blood. These pigs still showed most malnutrition symptoms after the food intervention period. MSB+ had superior influence on the GM development, exhibiting better performance in both structural and functional aspects. MSB+ pigs were colonized by less Proteobacteria but more Bacteroidetes, Firmicutes and Lachnospira spp. Pearson’s correlation analysis indicated a strong correlation between the abundance of mucosal e.g., Faecalibacterium and Lachnospira spp. and body weight, crown-rump length and total serum protein. In conclusion, the malnutrition symptoms were accompanied by an aberrant GM, and millet-based nutritional supplementation showed promising potentials to restore the reduced GM diversity implicated in pig malnutrition.