Oxide dispersion strengthened Fe-based steels are one of the candidate materials for applications in future nuclear reactors, an operation that needs superior mechanical properties and long-term microstructural stability at elevated temperatures. The effects of milling time on the hardness of nano-Y2O3 dispersed [Fe:(Cr-Mo-W-Ni-Nb-V)] nanocomposites were studied. The nanostructure, microstructure and crystallographic structure of the nanocomposites were evaluated using scanning electron microscopy (SEM), particle size analysis, X-ray diffraction (XRD), and high-resolution transmission electron microscopy (HR-TEM) and energy dispersive spectroscopy (EDS). The nanocomposites’ hardness was assessed by Vickers microhardness (HV). Milling up to 6 h yielded < 200 > textured plate-like particles of 200 nm thickness and 117 µm mean particle size due to particle-particle welding. Milling for 24 h resulted in a bimodal particle size distribution of 6 µm mean particle size due to strain hardening induced particle fracture. X-ray crystallite size of 24 h milled powder was 30 nm, corresponding to a dislocation density of 1.30 × 1015 /m2. Peak shift of (110) reflection with increasing milling time indicated that α-Fe matrix was under a compressive state of stress. Compositional fluctuations of alloying elements in the α-Fe matrix was detected even in 24 h milled powder by x-ray diffraction. Per TEM, uniformly dispersed ~ 20 nm Y2O3 particles of ~ 10 nm mean separation form an incoherent interface with the α-Fe matrix. The Vickers hardness of the nanocomposite increased from 185 to 537 -a ~ 300% after 24 h of milling. Such colossal increase in hardness was attributed to concurrent size effects associated with fracture, surface effects, solid solution strengthening in multicomponent alloys, and the Orowan mechanism.