Machining of austenitic stainless steels can result in different surface integrities and different machining process parameters will have a great impact on the component fatigue life. Understanding how machining processes affect the cyclic behaviour and microstructure are of outmost importance in order to improve existing and new life estimation models. Milling and electrical discharge machining (EDM) have been used to manufacture rectangular four-point bend fatigue test samples; subjected to high cycle fatigue. Before fatigue testing, surface integrity characterisation of the two surface conditions was conducted using scanning electron microscopy, surface roughness, residual stress profiles, and hardness profiles. Differences in cyclic behaviour were observed between the two surface conditions by the fatigue testing. The milled samples exhibited a fatigue limit. EDM samples did not show the same behaviour due to ratcheting. Recrystallized nano sized grains were identified at the severely plastically deformed surface of the milled samples. Large amounts of bent mechanical twins were observed ~ 5 μm below the surface. Grain shearing and subsequent grain rotation from milling bent the mechanical twins. EDM samples showed much less plastic deformation at the surface. Surface tensile residual stresses of ~ 500 MPa and ~ 200 MPa for the milled and EDM samples respectively were measured.