Although the major goals in manufacturing aircraft components include achieving ultimate longevity and steady operation, failure to function can still occur due to both environmental and operational conditions. As most of the failures come from their surfaces, increasing the surface characteristics to improve their overall performance has become a very important issue for many researchers. For this purpose, a surface-strengthening treatment technique like Severe Shot Peening (SSP) is widely used. SSP is a near-surface severe plastic deformation (NS-SPD) process that can form on the surface layers of the metallic material ultrafine-grains (UFGs) and nano-grains (NGs), thus leading to notable improvements in mechanical characteristics. In this work, the surface of an AMS 6265 steel broadly used in aircraft parts was subjected to a Severe Shot Peening (SSP) treatment to obtain a nanoscale surface modification (coarse-grained surface layer turns into a nano-crystalline surface layer), thus providing a surface hardening. To obtain proper microstructure and mechanical properties for both surface and core, before SSP, the AMS 6265 aircraft steel was subjected to a series of thermo-chemical treatments (case-hardening treatment). Nanoscale surface modification via SSP was achieved by cold local deforming of surface and near-surface layers using small steel balls commonly known as shots, forced towards the metallic surface using guns operating with compressed air. The effect of various processing conditions such as: steel ball size, air compression intensity, and treatment time on the microstructure and mechanical properties of AMS 6265 aircraft steel was analyzed. Structural characteristics like: constituent phases, lattice strain, crystallite size, and phase morphology, were studied, using SEM and X-ray diffraction techniques. The measured mechanical characteristics were: microhardness, ultimate tensile strength, yield strength, and elongation to fracture. The results were correlated with the SSP intensity to establish the best conditions for this deformation process, thus fitting the surface modification technology for the AMS 6265 aircraft steel.