We report the synthesis of alumina/stishovite nano-nano composite ceramics through a pressure-induced dissociation in Al2SiO5 at a pressure of 15.6 GPa and temperatures of 1300°C-1900°C. Stishovite is a high-pressure polymorph of silica and the hardest known oxide at ambient conditions. The grain size of the composites increases with synthesis temperature from ~15 to ~750 nm. The composite is harder than alumina and the hardness increases with reducing grain size down to ~80 nm following a Hall–Petch relation. The maximum hardness with grain size of 81 nm is 23 ± 1 GPa. A softening with reducing grain size was observed below this grain size down to ~15 nm, which is known as inverse Hall–Petch behavior. The grain size dependence of the hardness might be explained by a composite model with a softer grain-boundary phase.