Dynamic oscillatory shear and confocal laser scanning microscopy were used, respectively, to study the viscoelastic properties and ultrastructure of mixtures of unmodified waxy maize starch (3%) and gellan (0.005–0.05%), pasted at 75 and 90 °C. The two temperatures resulted in different rheological properties and ultrastructure. At 75 °C swollen and partially disrupted granules were observed, while at 90 °C the dominant feature was the presence of granule remnants. Addition of gellan produced mixtures with different elastic properties depending on the extent of granular disruption and gellan concentration in the mixture. Below 0.02% gellan, swollen and disrupted starch granules were surrounded by compact, yet slightly interconnected, gellan networks resulting in enhanced blends at both temperatures. Above such gellan concentration no enhancement was observed and gellan dominated the viscoelastic behavior of the mixtures because of the existence of more evenly distributed networks with swollen or disrupted starch granules exerting a weakening effect on the resulting structure.