We report the first identification of the optical bands of the B2Σ+-X2Σ+ system of AlO in the red supergiant VY CMa. In addition to TiO, VO, ScO, and YO, which were recognized in the optical spectrum of the star long time ago, AlO is another refractory molecule which displays strong emission bands in this peculiar star. Simulating the bands of AlO, we derive a rotational temperature of the circumstellar gas of Trot=700K. By resolving individual rotational components of the bands, we derive the kinematical characteristics of the gas, finding that the emission is centred at the stellar radial velocity and its intrinsic width is 13.5km/s (full width at half maximum). It is the narrowest emission among all (thermal) features observed in VY CMa so far. The temperature and line widths suggest that the emission arises in gas located within ∼20 stellar radii, where the outflow is still being accelerated. This result contradicts equilibrium-chemistry models which predict substantial AlO abundances only to within a few stellar radii. We argue that non-equilibrium models involving propagation of shocks are needed to explain the observations.