The fatigue damage behavior of three two-phase steels in the very high cycle fatigue regime (VHCF >108cycles) has been studied by both fatigue testing and microstructural investigation using SEM and TEM. The results show that the S-N curves can vary from a single to multi S-N curves, and there is also a transition of fatigue crack initiation from surface defect, subsurface defect such as inclusion to subsurface non defect area or matrix depending on the steel grades and its conditions. The surface crack initiation is caused by formation of irreversible slip bands at the free surface or around surface defect. Subsurface inclusion crack initiation is mainly caused by strain localization (slip bands) emanating at subsurface inclusion. Crack initiation in the subsurface non defect area occurs in the areas that are physically weak. It is also a fatigue damage process caused by micro cyclic plastic deformation. Formation of subsurface non defect fatigue crack origin is a crack initiation and propagation process.