High-energy ball milling (HEBM) of mixtures of iron powder and multi-walled carbon nanotube (MWCNT) has been performed in an attempt to synthesize nano-grained steel. Even after exposure to a harsh HEBM conditions, the MWCNTs are seen to have retained their structural identity, and therefore, an MWCNT-reinforced steel matrix composite could be finally produced. Moreover, the study has revealed that the minor addition of copper leads to a significant reduction in grain size of ferrite in the so-produced steel matrix–MWCNT composite. It is also noticed that the fine grain structure of ferrite remains intact even after consolidation of the powder composite by spark plasma sintering, followed by hot forging. The micro-hardness values obtained for the composites (with/without copper) are observed as comparable with the submicron-grained steels, so far reported in the literature.