A unique fabrication process termed high-pressure spark plasma sintering (HPSPS) enables fabrication of fully dense nanostructured ceramics. This makes it possible to investigate fundamental aspects of the mechanical behavior of nanostructured materials. The mechanical properties (such as strength and hardness) of polycrystalline materials typically improve with reduction of grain size, known as the Hall-Petch relationship. When reaching very fine nanoscale grains (<50 nm) the behavior changes and further reduction of the grain size may lower the mechanical properties. In the present study, nanostructured MgAl2O4 with an average grain size of about 20-40 nm was fabricated by HPSPS and deformed under using a microhardness Vickers indenter. Samples of the deformed area under the indentation tip were prepared by focused ion beam (FIB) and examined by scanning transmission electron microscopy (STEM) and transmission electron microscopy (TEM). Three different regions under the indentation were observed, a heavily strained region directly under the indentation, a virtually strain-free area far enough from the indentation and a transitional lightly strained region in between. Shear bands were also clearly observed throughout the deformed specimens. Analysis by Selected area electron diffraction (SAED) of the strained region confirmed misorientation of the grains, suggesting a large magnitude of grain boundary sliding and rotation. The microstructural evidence implies a combination of grain boundary sliding and dislocation deformation mechanism in the nanostructured material.