We study materials with spatial gradients in nanoscale grain size (5–120nm), and quantitatively examine the effect of spatial gradient on microstructure evolution and thermal stability using mesoscale Monte Carlo modeling and statistical analysis. The spatial grain size gradient weakens and the grain size distribution widens at elevated temperatures, accompanied by grain rounding and movement of grains along the gradient direction. Introducing heterogeneous grain boundary networks into gradient materials leads to better preservation of the spatial grain size gradient but less equiaxed grains. Coarsening in small grain regions is accompanied by an increase in the local fraction of low-energy grain boundaries, as these are competing mechanisms for reducing total energy, and spatial gradients in grain boundary character distribution and triple junction character distribution develop in the material. We further compare concave, linear, and convex gradient materials with increasing grain size gradient for small grains. Grains in convex gradient materials have the highest grain growth rate compared to grains of the same size in linear and concave gradient materials. The accelerated grain growth in the presence of a steeper grain size gradient is attributed to a change in local grain neighbor environment that promotes grain boundary curvature (and pressure) and enhances the driving force for grain growth.