Obesity threatens human health worldwide, and mounting findings have found that gut microbiota (GM) changes induced by diet intervention influence its development. This study aims to investigate the anti-obesity effects and GM changes of propionylated high-amylose maize starch (PS) in C57BL/6J mice fed with high-fat diet (HFD). In our results, PS decreased the body weight of HFD-fed mice after 8 weeks and regulated the glucose stability and insulin resistance. High-amylose maize starch (HAMS) and PS regulated the serum lipid levels and inflammatory response. Moreover, PS yielded more propionate relative to HAMS, proving that introduced propionyl groups could be released in the colon. 16S rRNA results showed that PS altered GM with the increase of bacteria (S24-7 and Ruminococcus) and decrease of harmful genera, which is linked to the anti-obesity effect. Our results provide a reference for the design of functional dietary fibers inducing high propionate production and GM modulation.