Early stages of surface relief evolution of persistent slip markings (PSMs), formed in areas where persistent slip bands (PSBs) intersect the free surface, in polycrystalline 316L stainless steel cycled with constant plastic strain amplitude were studied using atomic force microscopy (AFM) and electron backscattering diffraction (EBSD). Focused ion beam (FIB) technique was employed to obtain additional, more detailed information on the shape of PSMs. To reveal true qualitative and quantitative information on the simultaneous growth of intrusions and extrusions within individual PSMs, identical areas both on the specimen surface and on its inverse copy obtained via plastic replica were studied using AFM. Intrusions are preceded by extrusions regardless of orientation of individual grains of the polycrystal. The first intrusions appear largely around 1% of fatigue life at the moment when ‘static’ extrusions are developed. They appear predominantly but not exclusively at the side of extrusions where the emerging active slip plane is inclined to the surface at an acute angle. They grow faster than the stage of stable extrusion growth. Typical morphology of mature PSMs developed at 15% of fatigue life consists of ribbon-like extrusions accompanied by two thin parallel intrusions along both PSB–matrix interfaces. Experimental data on the morphology and growth of extrusions and intrusions are discussed in relation to the theoretical models and computer simulations of surface relief evolution leading to fatigue crack initiation.