Nanocrystalline ferrite has been produced in carbon steels with carbon content up to eutectoid composition through heavy work of rolling and ball milling. It was found that nanocrystallization of ferrite occurred at wavy band region with 0.1 mum thick and several mum long in heavy cold rolling and ball milling. During milling, the volume fraction of nanocrystalline band increases with increasing deformation degree until the complete nanocrystallization. The nanocrystalline ferrite was observed in all specimens irrespective of carbon content (0.03-0.89 mass%C) and starting microstructures (pearlite, ferrite or martensite). Together with the nanocrystallization of ferrite, the dissolution of cementite was observed in specimens with either pearlite or spheroidite structures. For the specimen with spheroidite structure, the formation of nanocrystalline ferrite around cementite particles seems to destabilize them and induced their dissolution. By aging the deformed specimens, recrystallization was observed by the appearance of large recrystallized grains (a few mum) in the work hardened regions, while in the nanocrystalline ferrite region only a slight grain growth to several tens of nanometers was observed instead of recrystallization. The fine grain of aged nanocrystalline ferrite is enhanced probably by the pinning effect of cementite particles precipitated at nanocrystalline ferrite grain boundaries.