Recently, there has been a large interest in the development of low carbon steels with ultra fine grain structure using lean chemistries. Although these steels typically have superior strength, the lack of work hardening capability limits the uniform elongation and thus the formability of these kinds of steels. It has been reported by Tsuji and co-workers (2002) that straining of martensite as an initial structure can yield an ultra fine grain structure with good combination of strength and ductility. However, the detailed mechanism of the grain refinement has not yet been clarified. In the present work, the annealing behavior of a low carbon martensitic structure with and without deformation at room temperature has been systematically studied. It is proposed that the process of concurrent softening due to recovery and recrystallization and precipitation of carbides is different for the deformed and undeformed materials. Further, preliminary results have been found on the role of substitutional alloying elements such as Mo or Cr on the kinetics of the softening processes.