Important functional properties of pizza cheese, such as meltability and stretchability, depend on the structural formation and interaction of casein gel and fat globules. The aim of this study was to understand the effects of modified starch on pizza cheese microstructure, and the resulting cheese functional properties. Pizza cheeses containing modified starches from various plant sources, and 9–22% rennet casein, were prepared. Starches were chosen based on their ability to form a gel, including gel rate, meting, hardness. Cheese texture and meltability were evaluated using Texture Profile Analysis (TPA) test and modified Schreiber melt test. Stretchability was scored using a pizza bake method. Cheese microstructure was observed under light microscopy using 3 dyes (iodine, fast green and Nile red) to specifically stain starch, protein and fat phases. Results show that microstructure and functionality of pizza cheese are changed by the addition of modified starch. Microscope images show that upon heating during pizza cheese process, modified starches completely cook out, and form a separate gel phase in the matrix. The modified starches enable formation of a continuous casein network, which improves stretching texture of melted cheese. Modified starch with reduced gelling rate (slower increase of elastic modulus G’ over time) enabled more phase separation, and greater stretching. Modified starch with more melted structure (greater loss of G’ during heating) contributed to larger cheese spread area in Schreiber test, and more fusing of cheese shreds in pizza bake test. Native starch, however, tended to form small gel pieces, interfering with the casein gel network, which restricted cheese stretchability after baking. This study indicates that modified starches and their blends alter cheese microstructure, leading to improved functionality. Starches, based on their functional properties, such as gelling rate and melting, can be used to improve cheese meltability and stretchability for specific formulations and applications, by enabling creation of a continuous casein gel network.