To design and develop advanced high-strength steels with desired properties, it is essential to understand the relationship between changes in steel microstructure caused by thermomechanical processing and the corresponding changes in their properties. Tailoring of cold rolling to promote the recovery process during annealing in single-phase steels is well understood. In contrast, HSS/AHSS consists of ferrite-pearlite as the initial cold-rolled microstructure. The early recovery behavior in the ferrite might be different from pearlite. Understanding the behavior of individual phases is important in optimizing the properties and design of AHSS. This study investigates the early recovery, recrystallization, and transformation during the different temperatures for various soaking times after 80% cold rolling. Mainly pearlite fraction and its distribution were varied in three HSS/AHSS to investigate the role of pearlite at different annealing temperatures in comparison to single ferrite consisting steel. It is quite challenging to differentiate recovery, recrystallization and phase transformation with only microscopy techniques due to subtle changes in structure. So we provide a comprehensive understanding of the correlative investigation across the multiple length scales using SEM, EBSD, TEM and nanoindentation. This study reveals the temperature and composition-driven recovery kinetics at different temperatures. A combination of electron microscopy and nanoindentation and a simple kinetics model enables new insights into what drives the kinetics and/or the dominating mechanisms at different temperatures. It was found that single ferrite consisting of steels resulted in recovery, and interestingly ferrite-pearlite consisting of HSS resulted in increasing hardness from the cold rolled state. Hardness increases show a clear dependence on the pearlite. The key substructural changes during early recovery and recrystallization such as carbon-defect interaction and rearrangement of defects were well captured and the corresponding hardness changes were quantified and the underlying mechanisms will be discussed.