To study the effects of Naematelia aurantialba (NA) on the rheological and gelatinization properties of starch, the processing methods of NA were diversified. In this study, the gelatinization and rheological properties of corn starch (CS) and edible cassava starch (ECS) were investigated by adding NA with different mass fractions. Starch soft candy was prepared using NA, CS, and ECS as the main raw materials. Rheological studies showed that both CS-NA and ECS-NA exhibited elastic modulus (G′) > viscosity modulus (G″), implying elastic behavior. G′ was such that CS+1%NA > CS+5%NA > CS+3%NA > CS > CS+2%NA > CS+4%NA > ECS+4%NA > ECS+3%NA > ECS+5%NA > ECS+2%NA > ECS+1%NA > ECS. The gelatinization implied showed that after adding NA, the pasting temperature of CS-NA and ECS-NA increased by 1.33 °C and decreased by 2.46 °C, while their breakdown values decreased by 442.35 cP and 866.98 cP, respectively. Through a single-factor test and orthogonal test, the best formula of starch soft candy was as follows: 0.4 f of NA, 10 g of white granulated sugar, a mass ratio of ECS to CS of 20:1 (g:g), 0.12 g of citric acid, 1 g of red date power, and 16 mL of water. The soft candy was stable when stored for two days. This study offers a new direction for the research and development of NA starch foods.