In present study, a novel physical modification of waxy maize starch (WMS) and normal maize starch (NMS) was investigated by using an atmospheric pressure plasma jet (APPJ) treatment. The effect on the structure and physicochemical properties of both starches was demonstrated by treatment with a 5% starch suspension (w/w) with APPJ for short periods of time (1, 3, 5, or 7 min). The pH of WMS and NMS was decreased after APPJ treatment from 5.42 to 4.94, and 5.09 to 4.75, respectively. The water-binding capacity (WBC) (WMS: 105.19%–131.27%, NMS: 83.56%–95.61%) and swelling volume (SV) (WMS: 2.96 g/mL–3.33 g/mL, NMS: 2.75 g/mL–3.05 g/mL) of the starches were obviously increased by APPJ treatment. The surfaces of starch granules were wrecked, due to plasma etching. No changes in the crystalline types of both starches were observed. However, the relative crystallinities (RCs) of WMS and NMS were reduced from 46.7% to 42.0%, and 40.1% to 35.7%, respectively. Moreover, the short-range molecular orders of both starches were slightly reduced. In addition, APPJ treatment resulted in lower gelatinization temperature and enthalpies. Therefore, APPJ provides a mild and green approach to starch modification, showing great potential for applications in the food and non-food industry.