Severe acute malnutrition (SAM) is associated with inadequate diet, low levels of plasma antioxidants and gut microbiota alterations. The link between gut redox and microbial alterations, however, remains unexplored. By sequencing the gut microbiomes of 79 children of varying nutritional status from three centers in Senegal and Niger, we found a dramatic depletion of obligate anaerobes in malnutrition. This was confirmed in an individual patient data meta-analysis including 107 cases and 77 controls from 5 different African and Asian countries. Specifically, several species of the Bacteroidaceae, Eubacteriaceae, Lachnospiraceae and Ruminococceae families were consistently depleted while Enterococcus faecalis, Escherichia coli and Staphylococcus aureus were consistently enriched. Further analyses on our samples revealed increased fecal redox potential, decreased total bacterial number and dramatic Methanobrevibacter smithii depletion. Indeed, M. smithii was detected in more than half of the controls but in none of the cases. No causality was demonstrated but, based on our results, we propose a unifying theory linking microbiota specificity, lacking anaerobes and archaea, to low antioxidant nutrients, and lower food conversion.