This work unravels structure-property correlations at the micrometer length scale during recovery and early recrystallization of a cold rolled high strength steel comprised of ferrite and pearlite. High resolution nano-indention mapping is used to measure the hardness of ferrite, pearlite and the transition zone between them, which correlates well with the local microstructure obtained from scanning and transmission electron microscopy. A clustering algorithm is used to determine the properties of the constituent microstructural features. The variation in the hardness of the phases with annealing temperature agrees well with the dislocation activity observed using Transmission Electron Microscopy (TEM) and a simple mechanism to reconcile the observations is presented. © 2020 Acta Materialia Inc.