The composition and structure of gut microbiota plays an important role in obesity induced by a high-fat diet (HFD) and related metabolic syndrome (MetS). Previous studies have shown that galacto-oligosaccharides (GOSs) have an effective anti-obesity effect. In this study, we aimed to investigate the effect of enzymatically synthesized α-galacto-oligosaccharides (ES-α-GOSs) on MetS and gut microbiota dysbiosis in HFD-fed mice, and to further investigate whether the attenuation of MetS is associated with the modulation of gut microbiota. Our results indicated that ES-α-GOS could notably ameliorate obesity-related MetS, including hyperlipidemia, insulin resistance and mild inflammation. The subsequent analysis of gut microbiota further showed that ES-α-GOS supplements can significantly modulate the overall composition of the gut microbiota and reverse the gut microbiota disorder caused by HFD feeding. Moreover, Spearman correlation analysis showed that 40 key bacteria reversed by ES-α-GOS were highly associated with metabolic parameters. These results suggested that ES-α-GOSs could serve as a potential candidate for preventing obesity-induced MetS in association with the modulation of gut microbiota.