The response of the structure of the M-type barium hexaferrite (BaFe12O19) to mechanical action through high-energy milling and its impact on the magnetic behaviour of the ferrite are investigated. Due to the ability of the Fe-57 Mossbauer spectroscopic technique to probe the environment of the Fe nuclei, a valuable insight on a local atomic scale into the mechanically induced changes in the hexagonal structure of the material is obtained. It is revealed that the milling of BaFe12O19 results in the deformation of its constituent polyhedra (FeO6 octahedra, FeO4 tetrahedra and FeO5 triangular bi-pyramids) as well as in the mechanically triggered transition of the Fe3+ cations from the regular 12k octahedral sites into the interstitial positions provided by the magnetoplumbite structure. The response of the hexaferrite to the mechanical treatment is found to be accompanied by the formation of a non-uniform nanostructure consisting of an ordered crystallite surrounded/separated by a structurally disordered surface shell/interface region. The distorted polyhedra and the non-equilibrium cation distribution are found to be confined to the amorphous near-surface layers of the ferrite nanoparticles with the thickness extending up to about 2 nm. The information on the mechanically induced short-range structural disorder in BaFe12O19 is complemented by an investigation of its magnetic behaviour on a macroscopic scale. It is demonstrated that the milled ferrite nanoparticles exhibit a pure superparamagnetism at room temperature. As a consequence of the far-from-equilibrium structural disorder in the surface shell of the nanoparticles, the mechanically treated BaFe12O19 exhibits a reduced magnetization and an enhanced coercivity.