Child stunting is an indicator of chronic undernutrition and reduced human capital. However, it remains a poorly understood public health problem. Small-quantity lipid-based nutrient supplements (SQ-LNS) have been widely tested to reduce stunting, but have modest effects. The infant intestinal microbiome may contribute to stunting, and is partly shaped by mother and infant histo-blood group antigens (HBGA). We investigated whether mother-infant fucosyltransferase status, which governs HBGA, and the infant gut microbiome modified the impact of SQ-LNS on stunting at age 18 months among Zimbabwean infants in the SHINE Trial ( NCT01824940 ). We found that mother-infant fucosyltransferase discordance and Bifidobacterium longum reduced SQ-LNS efficacy. Infant age-related microbiome shifts in B. longum subspecies dominance from infantis , a proficient human milk oligosaccharide utilizer, to suis or longum , proficient plant-polysaccharide utilizers, were partly influenced by discordance in mother-infant FUT2+/FUT3- phenotype, suggesting that a "younger" microbiome at initiation of SQ-LNS reduces its benefits on stunting.