Rolling-sliding contact fatigue experiments were performed on through hardened (TH) 100Cr6 and surface induction hardened (SIH) C56E2 bearing steels to study the effect of heat treatment procedure and hardness difference on their wear and/or surface-initiated damage. The heat-treated microstructures included tempered martensite without the presence of retained austenite. It was found that initial stress distribution below the surface of TH specimens remains close to zero with respect to the depth, while, employing SIH resulted in relatively high compressive residual stresses. The wear damage of the specimens was characterized for negative ΔH (i.e., specimen's hardness minus counterpart's hardness) subjected to rolling-sliding contact in a twin-disc configuration operated under a mixed lubrication condition. According to the wear mechanisms and damages assessed, three regions were distinguished: i) mild wear and onset of micropitting, ii) transition region from mild to severe micro-pitting and iii) severe micro-pitting wear. Decreasing the ΔH resulted in a gradual increase in the wear rate of TH specimens, while, the increase in the wear rate of SIH specimens was delayed; with a same absolute hardness, TH specimen with a ΔH of −84 HV already reached the third wear region, while a SIH specimen with a ΔH of −150 HV still operates in the second region. Inspection of the affected subsurface unveiled the response of worn microstructures to the etchant and how the micro-cracks could possibly form within the wear affected zone. The results obtained were mainly explained based on the state of the residual stresses, possible contributions of the microstructural features, and wear behavior (material removal) of the specimen.