The advanced thermomechanical treatment including cold rolling and subsequent annealing of the microstructures with high percentage of martensite is one of the effective methods for grain refinement in steels. In this research, this treatment was applied on a low-alloy carbon steel with the bainitic-martensitic microstructure. Effect of bainite phase on microstructure evolution during this treatment was investigated. Color metallography was performed for determination of the type and percentage of phases. Specimens with high percentage of bainite and martensite were detected and cold rolled with different reductions and subsequently annealed at different times and temperatures. Microstructural evolutions were characterized using optical and scanning electron microscopes in different stages of the process. Effects of annealing time and temperature and amount of cold deformation were investigated. Mechanical properties of the specimens were determined by hardness and uniaxial tensile tests. The results showed that deformation of bainitic and martensitic microstructures during cold rolling resulted in a drastic increase of the nucleation sites for recrystallization of ultrafine ferrite grains during annealing. Microstructural evaluations in the bainitic-martensitic specimen revealed that after annealing of the specimens cold rolled up to 70%, 80% and 90%, the lowest grain size was about 350, 300 and 125 nm, respectively. The final microstructure was consisted of equiaxed grains of ferrite, nano-sized carbide precipitates and islands of tempered martensite. Mechanical properties of the ultrafine grained microstructure were improved compared to the initial microstructure. The results obtained from the specimen with the martensitic microstructure subjected to the similar thermomechanical treatment revealed that the final grain size and hardness was approximately similar to the bainitic-martensitic specimen. However, due to the lower hardness of bainite phase, cold rolling of the bainitic-martensitic microstructure was much easier than the martensitic one, resulting in no transverse cracks in the cold rolled specimen. This work clearly showed that bainite is a suitable phase as starting microstructure for grain refinement of steels by the advanced thermomachanical processing.