The use of higher strength steels allows the design of lighter, slenderer and simpler structures. Nevertheless, the increase of the yield strength of the steels does not correspond to a proportional increase of fatigue resistance, which makes the application of high strength steels on structures prone to fatigue, a major concern of the design. This paper presents a comparison of the fatigue behavior between the S355 mild steel and the S690 high strength steel grades, supported by an experimental program of fatigue tests of smooth specimens, performed under strain control, and fatigue crack propagation tests. Besides the cyclic elastoplastic characterization, the fatigue tests of smooth small size specimens allow the assessment of the fatigue crack initiation behavior of the materials. Results show that the S690 steel grade presents a higher resistance to fatigue crack initiation than the S355 steel. However, the resistance to fatigue crack propagation is lower for the S690 steel grade, which justifies an inverse dependence between static strength and fatigue life, for applications where fatigue crack propagation is the governing phenomenon. Consequently, the design of structural details with the S690 steel should avoid sharp notches that significantly reduce the fatigue crack initiation process.