We demonstrate the capability of a novel Electron Backscatter Diffraction (EBSD) dictionary indexing (DI) approach by means of orientation mapping of a highly deformed graded microstructure in a shot peened Aluminium 7075-T651 alloy. A low microscope accelerating voltage was used to extract, for the first time from a bulk sample, statistically significant orientation information from a region close to a shot crater, showing both recrystallized nano-grains and heavily deformed grains. We show that the robust nature of the DI method allows for faster acquisition of lower quality patterns, limited only by the camera hardware, compared to the acquisition speed and pattern quality required for the conventional Hough indexing (HI) approach. The proposed method paves the way for the quantitative and accurate EBSD characterization of heavily deformed microstructures at a sub-micrometer length scale in cases where the current indexing techniques largely fail.