High amylose maize starch (HAMS) and waxy maize starch (WMS) were modified by propionylation and their corresponding physicochemical characteristics, digestion and fermentation properties were studied. The results indicated that two new peaks related to methylene (2.20 ppm) and methyl (0.97 ppm) in the NMR spectrum were formed, indicating the occurrence of propionylation, and this was further confirmed by the formation of a characteristic absorption at 1747 cm−1 in the FTIR spectrum. The propionylation led the modified starch having a lower electron density contrast between the crystalline and amorphous flakes, resulting in the formation of a more compact structure following the increased degrees of substitution (DS). The propionylated starch also had a higher thermal stability and hydrophobicity. These structural changes increased the content of resistant starch (RS) and reduced the predicted glycemic index. More importantly, the gut microbiota fermentation properties indicated that the propionylation of the starch can not only increase the yield of propionate, but also increase the concentration of total short-chain fatty acids (SCFAs). This study highlights a new approach to significantly enhance the RS content in starch, together with an increased SCFA generation capacity.