Using molecular dynamics simulations of UO2-a type II superionic conductor-we identify a well-defined onset of dynamic disorder (Tα), which is remarkably correlated to a nontrivial advance of dynamical heterogeneity (DH). Quantified by the correlations in the dynamic propensity and van Hove self-correlation function, the DH is shown to grow with increasing temperature from Tα, peak at an intermediate temperature between Tα and Tλ-the superionic transition temperature-and then recede. Surprisingly, the DH attributes are not uniform across the temperatures-our investigation shows a low temperature (αT) stage DH, which is characterized by weak correlations and a plateaulike period in the correlations of the propensity, and a high temperature (λT) stage DH with strong correlations that are analogous to those in typical supercooled liquids. Our work, which has rigorously identified the onset of superionicity, gives a different direction for interpreting scattering experiments on the basis of statistical, correlated dynamics.