The pasting and rheological properties and the microstructure of normal cornstarch (CS) and waxy cornstarch (WCS) mixed with soy protein isolate (SPI) were characterized before and after dry heating using a rapid visco analyser (RVA), a rheometer, and by scanning electron microscopy (SEM). Dry heating with SPI led to a significant increase in starch viscosity; the increase in viscosity of WCS was observed to be more pronounced than that of CS. There was a significant increase in the G′ and G′′ values and a corresponding decrease in the tan δ value of the dry heated mixtures, compared to those of untreated starch. This indicated an increase in gel network structure formation in pasted starch after dry heating; in fact, the gel network of heated pasted starch became more solid-like compared to that observed in untreated starch. The SEM images revealed the occurrence of starch accumulation after dry heating of starch with SPI; in addition, compared to CS/SPI, WCS/SPI was observed to form a larger lump. The accumulation of starch molecules suggested the occurrence of interactions between starch and SPI after dry heating; the interactions of WCS and SPI were more pronounced than those of CS and SPI. This simple heating process (with SPI) could be used as a promising method for the modification of WCS.